Consider the graph given below as : Which one of the following graph is…

2014

Consider the graph given below as :

Which one of the following graph is isomorphic to the above graph ?

Attempted by 41 students.

Show answer & explanation

Approach: To determine isomorphism, compare degree sequences and the local neighbourhood structure, then produce an explicit one-to-one vertex mapping that preserves edges.

Step 1: Degree and neighbourhood check

  • Observe that every vertex in the original drawing has the same degree pattern (each vertex is connected to three neighbours in the layout). Any isomorphic candidate must have the same degree for each corresponding vertex.

  • Beyond degrees, compare which vertices are corner vertices (on the outer square) versus inner vertices and which vertices have two neighbours in adjacent columns versus one in the same column. These local patterns are preserved under isomorphism and help pick candidates for the mapping.

Step 2: Provide an explicit isomorphism

A concrete vertex mapping from the original graph (u1,...,u8) to the vertices of the correct drawing (v1,...,v8) that preserves all adjacencies is:

  • u1 -> v1

  • u5 -> v4

  • u2 -> v2

  • u6 -> v6

  • u3 -> v3

  • u7 -> v7

  • u4 -> v8

  • u8 -> v5

Step 3: Verify adjacency preservation

  • Check a few representative edges: the vertical pair u1–u5 maps to v1–v4 (outer left vertical edge); cross connections from a top vertex to adjacent bottom-column vertices in the original map to the corresponding diagonal/interior edges in the candidate drawing.

  • Because the mapping pairs vertices with identical degree and identical types of neighbourhood (corner vs inner, and which columns they connect to), every original edge corresponds to an edge in the candidate drawing and vice versa.

Conclusion: The candidate drawing in the correct option is isomorphic to the given graph via the mapping above, so that option is the correct choice.

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

Explore the full course: Mppsc Assistant Professor