GATE CS Mastery
Cheat sheets

GATE CS 2012 · Engineering Mathematics

Question 26

MCQPrinted as CS Q.262 marksWrong answer: −2/3Medium (estimate)

Question

Which of the following graphs is isomorphic to the given graph?

Given graph with 8 vertices (a 5-cycle with a centre vertex of degree 4, a pendant vertex on the centre and a 2-edge path hanging from the centre) and four candidate graphs A to D; in candidate B the left vertex is joined by a long curved edge to the top-right vertex.
Stem graph and options (A), (B), (C), (D)
Choose one option
Official answer and solution
Official answer
B
From
Official GATE 2012 answer key

Solution

Compare structural graph invariants: degree sequences, cycle lengths, and vertex neighborhoods between the stem graph and the options.

  1. Analyze the given stem graph:
  • Total vertices = 8.
  • Degree sequence: Two vertices have degree 1 (pendant vertices), five vertices have degree 2, and one vertex has degree 4. In sorted order: [1, 1, 2, 2, 2, 2, 2, 4].
  • Cycle structure: The graph contains a central 5-cycle (pentagon). The degree-4 vertex is part of this 5-cycle and connects to two external pendant vertices of degree 1.
  1. Inspect the candidate options:
  • Graph (A): Does not match the cycle structure or degree sequence.
  • Graph (C) and (D): Their cycle lengths or pendant attachments differ from the stem graph.
  • Graph (B): Contains exactly 8 vertices with degree sequence [1, 1, 2, 2, 2, 2, 2, 4]. It possesses a 5-cycle with the degree-4 vertex belonging to the 5-cycle and having two attached pendant vertices of degree 1. An explicit bijective mapping of vertices preserves adjacency between the stem graph and Graph (B).
  1. Therefore, Graph (B) is isomorphic to the stem graph.
Final answer

B

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2012 Computer Science and Information Technology (CS)
Question
26 of 65, printed as CS Q.26
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.