GATE CS 2012 Q26 — Graphs: Connectivity, Matching, Colouring

To determine which graph is isomorphic to the given graph, we can use basic graph invariants such as the number of vertices, number of edges, degree sequence, and the presence of cycles of specific lengths.

1. Analyze the Given Graph

• Number of vertices ($V$): $8$
• Number of edges ($E$): $12$
• Degree sequence: It is a $3$-regular graph (every vertex has a degree of $3$).
• Bipartiteness: The given graph is bipartite. We can partition its vertices into two independent sets of size $4$ such that there are no edges between vertices of the same set. Since it is bipartite, it contains no odd cycles (no cycles of length $3$ or $5$).

2. Eliminate Options

• Option A: Contains triangles (cycles of length $3$). Since the given graph has no triangles, Option A is not isomorphic.
• Option C: Contains triangles (cycles of length $3$). Thus, Option C is not isomorphic.
• Option D: Contains triangles (cycles of length $3$). Thus, Option D is not isomorphic.
• Option B: Like the given graph, it is a $3$-regular bipartite graph on $8$ vertices with no odd cycles. A bijective mapping can be established between the vertices of the given graph and Option B, confirming they are isomorphic.

Therefore, the correct option is B.