GATE 2012 CS (CS1) – Question 36

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple choice

Which graph A,B,C,D is isomorphic to the given graph?

Diagram for GATE 2012 CS (CS1) question 36

Graph A
Graph B
Graph C
Graph D

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) Graph B

Explanation

The given graph has a five-cycle with a degree-four vertex. That vertex has one additional leaf attached directly and another leaf attached through a two-edge path. Matching both the degree sequence and the adjacency of high-degree vertices rules out the other drawings. Graph B admits the required adjacency-preserving relabelling, so B.

More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions

GATE 2013 CS (CS1) Q35 – For undirected graphs, P: The number of odd-degree vertices is even. Q: The sum of all…
GATE 2013 CS (CS1) Q36 – The line graph L(G) has one vertex per edge of simple G, and joins vertices iff their G…
GATE 2011 CS (CS1) Q27 – The drawings show complete graph K₄ and cube graph Q₃. Which is true?
GATE 2010 CS (CS1) Q11 – For graph G=(V,E), let (G)= di dd, where i d counts vertices of degree d. If different…
GATE 2010 CS (CS1) Q38 – Which sequences cannot be degree sequences of simple graphs? I: 7,6,5,4,4,3,2,1 II:…
GATE 2015 CS (CS2) Q61 – A self-complementary graph is isomorphic to its complement. What must its vertex count n…

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →