Bob removed a degree 3 node in an n-vertex tree, how many connected components a
ID: 3203809 • Letter: B
Question
Bob removed a degree 3 node in an n-vertex tree, how many connected components are in the resulting graph? (An expression that may contain n.) Given an n-vertex tree, Bob added 10 edges to it, then Alice removed 5 edges and the resulting graph has 3 connected components. How many edges must be removed to remove all cycles in the resulting graph? (An expression that may contain n) Give a gray code for 3-bit strings. (Recall, that a gray code is a sequence of the strings where adjacent elements differ by one. For example, the gray code of 2-bit strings is 00, 01, 11, 10 Note the last string is considered adjacent to the first and 10 differs in one bit from 00. Answer should be sequence of three-bit strings: 8 in all) For all n greaterthanorequalto 3, the complete graph on n vertices, K_n has more edges than the d-dimensional hypercube for d n. (True or False.) The complete graph with n vertices where n is an odd prime can have all its edges covered with x Rudrata cycles: a cycle where each vertex appears exactly once. What is the number, x, of such cycles in a cover? (Answer should be an expression that depends on n.) Give a set of disjoint Rudrata cycles that covers the edges of K_5, the complete graph on 5 vertices. (Each path should be a sequence (or list) of edges in K_5.Explanation / Answer
a.
There are 3 connected components in the resulting graph.
Since a degree 3 node is removed, each neighbour node now comes into 3 different connected components.
b.
Bob added 10 edges and Alice removed 5 edges. Hence there are 10-5= 5 extra edges.
That is n-1+5=n+4 total edges in the graph.
There are 3 connected components.
Now in order to remove cycles and to form three graphs, number of graphs needed are n1-1,n2-1 and n3-1 edges are required, where n1+n2+n3=n.
Edges required are n-3
Hence n+4-(n-3)= 7 edges must be removed
c.
Gray codes for 3 bit strings
000
001
011
010
110
111
101
100
d.
For a complete graph, Number of edges= n(n-1)/2
For a Hypercube, Number of edges= n(2n-1)
For all n>3, n(2n-1)>n(n-1)/2.
Hence the above statement is false and a hypercube has more edges than a n vertex complete graph.