GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 29

Question

Which of the following is/are possible for unlabelled trees/graphs? (Mark all the appropriate choices)

• A. Two different trees with the same number of vertices and the same number of edges.
• B. Two different simple graphs with $8$ vertices all of degree $2.$
• C. Two different simple graphs with $5$ vertices all of degree $4.$
• D. Two different graphs with $7$ vertices all of degree $3.$

Answer 1

B is possible as we can have one connected cycle graph of 8 vertices and the second one a disconnected graph containing 2 cycles of 4 vertices each. For a connected graph there is only one possibility.

C is not possible because it is the complete graph and there is only one complete graph over $n = 5.$

D is not possible because sum of degrees $ = 7 \times 3 = 21-$ and odd number which is not possible for degree sum.

Correct answer: A;B.