Please give detailed responses and work to all problems! Thank you!! 1. At the e
ID: 2970477 • Letter: P
Question
Please give detailed responses and work to all problems! Thank you!!
1. At the end of a party with n people, everybody knows everybody else. Draw the graph representing this situation. How many edges does it have?
2. How many graphs are there on 20 nodes?
3. Find all graphs that are paths or cycles and whose complements are also paths or cycles.
4. (a.) We delete an edge e from a connected graph G. Show by an example that the remaining graph may not be connected.
(b.) Prove that is we assume that the deleted edge e belongs to a cycle that is a subgraph of G, then the remaining graph is connected.
5. Prove that a graph with n nodes and more than ( n-1 choose 2 ) edges is always connected.
Explanation / Answer
1. the graph will be a complete graph with n vertices. that is if u select any two vertices, there will exist an edge between them. so if u pick any vertex, it will be adjacent to all the other vertices. number of edges is equal to the number of ways of choosing any two points among n points=nC2=n(n-1)/2
2. two graphs having 20 vertices will be different if it differs in edges between two points, that is to say, if one graph has an edge between a and b and the other doesnt then they will be different. Take two points, then we have two cases, either there is an edge between them or there is not. so for any two points we have 2 cases and number of ways of selecting two points is n(n-1)/2 . so total number of graphs is 2^(n(n-1)/2), put n=20 in this we get, 2^190.
4.a. take graph having vertices a, b, c, d and edges ab,bc,cd. then it is connected graph, that is between any two points we have a path. now if we remove the edge bc, then we dont have a path from a to d (earlier we had a path ab.bc.cd from a to d). so it is disconnected.
4.b. suppose the edge deleted between a and b belongs to a cycle a,a1,a2,a3,....,an,b,a . given G is connected before deleting. so for any two points x,y we have a path, say x,x1,x2,....,xn,y. now we delete the edge ab, then two cases arise, 1st edge ab lies in the path of x,y ,2nd edge ab does not lie in path of x,y. case 1: ab lies in the path, then xx1=ab or x1x2=ab or x2x3=ab or.....or xny=ab, wherever we get ab we replace it with the path aa1a2a3....anb. so even after removing ab in path xy, we get a new path sonsiting of aa1a2a3....anb. so again after removing ab, x and y are conneced.2nd case: if ab does not lie in the path, then is no difference in the path between x and y after removing ab. Hence in any case we get a path from any two points x and y.Hence the graph will remain connected
5.Given that number of edges say E, is greater than (n-1)C2 where n is number of edges. we prove this by contradiction. suppose graph is not connected. then we get two disjoint graphsG1 and G2 such that G=G1 union G2. with |G1|=k and |G2|=n-k, 0<k<n. If we connect all the vertices of G1 and G2 to form a graph G3 then number of edges in G3 less than or equal to nC2 (Since G3 has at most complete graph edges.) but : (n-1)C2+1 + k.(n-1) less than or equal to number of egdes of G3=nC2. this implies, (k-1)(n-k-1)+1 less than or equal to 0 this contradiicts that 0<k<n. Hence G has to be connected.