Which of the following graphs is isomorphic to

2012

Which of the following graphs is isomorphic to

Attempted by 125 students.

Show answer & explanation

Key idea: use the degree sequence and cycle structure to test for isomorphism.

  1. Step 1: Identify distinguishable features in the original graph.

    • A single central hub vertex that connects the left leaves and the right cluster.

    • A 3‑cycle (triangle) forming the right cluster, attached to the hub.

    • Three pendant (leaf) vertices attached to the hub on the left.

  2. Step 2: Compare each candidate graph to these features.

    • Look for a vertex that can serve as the hub (same degree and attachments).

    • Confirm there is a 3‑cycle connected to that hub and three leaves attached to it.

  3. Step 3: Find a vertex-to-vertex mapping for the matching graph.

    • Map the central hub of the original to the central hub in the matching graph.

    • Map the three vertices that form the right-hand triangle to the three triangle vertices in the matching graph.

    • Map each left-side leaf to the corresponding leaf attached to the hub.

  4. Conclusion: The only candidate that preserves the hub with three attached leaves and the separate 3‑cycle attached to that hub is the graph that shows the triangle attached to the central vertex and three leaves on the left. Therefore that graph is isomorphic to the original.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir