Graph Isomorphism MCQs and NATs: 12 Solved Questions on Detection and Counting

Graph isomorphism questions are difficult because the drawing can distract you from the graph. Two pictures may look different while encoding the same adjacency relation, and two similar pictures may fail because of one invariant. Attempt every item before reading its answer, and write down what convinced you.

Choose an option for each multiple-choice question, and enter a number for each numerical-answer question. The linked worked solutions provide additional detail when an answer needs a second pass.

1. Graph isomorphism definition and self-complementary conditions

An isomorphism is a bijection between two vertex sets that preserves adjacency in both directions. Vertex count, edge count and degree sequence are quick invariants. Matching values are necessary, not sufficient, but one mismatch proves that two graphs are not isomorphic.

Q1. Definition of isomorphic graphs

MCQ

Two graphs that have the same structure and can be matched vertex to vertex and edge to edge are called:

• A. Complete

• B. Isomorphic

• C. Connected

• D. Complementary

Answer: B. Isomorphic.

The matching is a bijection between vertex sets, and an edge exists between two vertices exactly when an edge exists between their images. Labels and positions may change, but the incidence structure cannot.

Q2. Order of a self-complementary graph

MCQ

A graph is self-complementary if it is isomorphic to its complement. For all self-complementary graphs on 𝑛 vertices, 𝑛 is

• A. A multiple of 4

• B. Even

• C. Odd

• D. n ≡ 0 (mod 4) or n ≡ 1 (mod 4)

Answer: D.

A self-complementary graph contains half of the n(n-1)/2 possible edges, so m=n(n-1)/4 must be an integer. For n=4k or 4k+1, the product n(n-1) is divisible by 4; for 4k+2 or 4k+3, it leaves remainder 2. Thus n=5 gives m=5, while n=6 would give m=7.5, which is impossible. See the exact solved question.

Q3. Cycle isomorphic to its complement

Numerical answer

A cycle on n vertices is isomorphic to its complement. The value of n is _____.

Answer: 5.

Every vertex of C_n has degree 2. Its complement has degree (n-1)-2=n-3, so isomorphism requires 2=n-3, giving n=5. The complement of a five-cycle is indeed another five-cycle, which confirms the result on the exact solved question.

2. Detecting isomorphism in graph drawings

For each visual question, first write the signature (vertices, edges, sorted degree sequence, components, triangles). If it survives, inspect how distinctive vertices, cycles and leaves connect.

Q4. Match a degree-4 hub, a five-cycle and two pendant branches

MCQ

Which of the following graphs is isomorphic to

• A.

  

• B.

  

• C.

  

• D.

  

Answer: B.

First match the degree sequence 4,2,2,2,2,2,1,1 and reject any option that differs. In option B the degree-4 hub carries a five-cycle, one pendant vertex and one pendant path of length two, exactly as the source graph does. Open the exact solved question.

Q5. Select the isomorphic pair

MCQ

Consider the following graph shown below:

Which of the following given pairs are isomorphic:

• A. G1 and G2

• B. G3 and G4

• C. G2 and G3

• D. Both B and C

Answer: B. G3 and G4.

G3 and G4 are two drawings of the cube graph: each has eight degree-3 vertices and the same adjacency structure. G1 and G2 can be rejected by comparing their preserved cycle structures, not their visual shapes.

Q6. Verify an explicit vertex correspondence

MCQ

I)

II)

Choose the correct statement about these two graphs

• A. Both I, II have same number of edges, but not isomorphic

• B. I, II does not have the same number of edges, thus not isomorphic

• C. I, II have same number of edges, also isomorphic

• D. These two graphs cannot be checked for isomorphism

Answer: C.

Neither drawing carries vertex labels, so start by marking the highest-degree vertex in each one. Both graphs have 6 vertices, 11 edges and degree sequence 5,4,4,3,3,3, and in each drawing that degree-5 vertex is joined to every other vertex. Deleting it leaves the complete bipartite graph K2,3 in both cases, so mapping hub to hub and then matching the remaining vertices by degree gives a bijection that preserves adjacency in both directions.

3. Cycle structure and local-neighbourhood checks

Equal degree sequences can leave several candidates. Compare triangles, simple-cycle counts, bipartiteness and the neighbour degrees of distinctive vertices before attempting a full mapping.

Q7. Use minimum degree to force one cycle

MCQ

For a simple undirected graph with 4 edges, the maximum possible value of the minimum degree is 2. How many non-isomorphic graphs achieve this value?

• A. 1

• B. 15

• C. 10

• D. Data insufficient

Answer: A. 1.

With four edges, the degree sum is 8. If the minimum degree is 2, every vertex has degree at least 2, so 2n <= 8 and n <= 4. A simple graph with four edges needs at least four vertices because K3 has only three edges. Therefore n=4, every degree is exactly 2, and the only simple 2-regular graph on four vertices is C4. There is one isomorphism class.

Q8. Choose the drawing with the same neighbourhood pattern

MCQ

Consider the graph given below as :

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

• A.

  

• B.

  

• C.

  

• D.

  

Answer: C.

Apply u1 -> v1, u2 -> v3, u3 -> v5, u4 -> v7, u5 -> v4, u6 -> v2, u7 -> v6, u8 -> v8. Check one vertex in full: u1 is joined to u5, u6 and u7, and their images v4, v2 and v6 are exactly the three neighbours of v1 in option C. Then check a missing edge, because u1 and u8 are not adjacent and neither are v1 and v8. Adjacency is preserved in both directions, which is stronger than matching degrees.

4. Counting non-isomorphic simple graphs

Count structures, not vertex labels. Partition the cases by edges, components and degree sequences, then name every isomorphism class.

Q9. Three vertices

Numerical answer

How many simple non isomorphic graphs are possible with 3 vertices ?

Answer: 4.

Classify by edge count: the empty graph, one edge plus an isolated vertex, the path P3, and the triangle K3. These have 0, 1, 2 and 3 edges respectively, so no two classes can be isomorphic.

Q10. Four vertices and three edges

Numerical answer

How many simple non isomorphic graphs are possible with 4 vertices and 3 edges ?

Answer: 3.

The connected cases are the trees K1,3, with degree sequence (3,1,1,1), and P4, with (2,2,1,1). The only disconnected case is K3 plus an isolated vertex, with (2,2,2,0). Therefore there are three classes.

Q11. Five vertices and three edges

Numerical answer

How many simple non isomorphic graphs are possible with 5 vertices and 3 edges ?

Answer: 4.

The four classes are K3 plus two isolated vertices, P4 plus one isolated vertex, K1,3 plus one isolated vertex, and the disjoint union of P3 and K2. A connected graph on five vertices needs at least four edges, so no connected case is missing.

Q12. Eight vertices, eight edges and equal degree

Numerical answer

How many simple non isomorphic graphs are possible with 8 vertices and 8 edges, such that degree of every vertex must be same ?

Answer: 3.

If the common degree is r, the handshaking lemma gives 8r=2(8)=16, hence r=2. Every finite simple 2-regular graph is a disjoint union of cycles, and the partitions of 8 into parts of at least 3 are 8, 5+3 and 4+4. They give C8, C5 disjoint union C3, and C4 disjoint union C4.

5. A reliable graph-isomorphism checklist

1. Reject fast. Compare vertex count, edge count, component count and sorted degree sequence. One mismatch ends the test; a complete match only earns a second check.

2. Refine structurally. Compare triangles, cycle lengths, bridges, cut vertices, bipartiteness and neighbour-degree multisets.

3. Prove. Give a bijection and test every edge, or give representative checks plus a general adjacency rule.

For a positive example, let G have vertices {a,b,c,d,e,f} and edges {ab,bc,ca,ad,be,cf}. Let H have edges {13,35,51,12,34,56}. The map a->1, b->3, c->5, d->2, e->4, f->6 sends the six edges to 13, 35, 51, 12, 34, 56, exactly the edge set of H, so the graphs are isomorphic.

Now compare K3,3 with the triangular prism {12,23,31,45,56,64,14,25,36}. Both have 6 vertices, 9 edges and degree sequence (3,3,3,3,3,3). The prism has triangles (1,2,3) and (4,5,6), while K3,3 is bipartite and triangle-free, so they are not isomorphic.

6. How graph isomorphism is examined and where students slip

Use five exam moves: recall the definition in Q1, derive self-complementary conditions in Q2 and Q3, test drawings with invariants and bijections in Q4 to Q6 and Q8, force a cycle from degree conditions in Q7, and count unlabelled structures in Q9 to Q12.

The common traps are trusting layout, treating equal degree sequences as sufficient, forgetting isolated components, counting labelled versions as distinct, and missing that every 2-regular component must be a cycle of length at least 3. For a broad survey of degree, Euler and Hamiltonian graphs, planarity, colouring and trees, use Graph Theory MCQs: 12 Solved Euler, Coloring, Trees; this set stays with isomorphism invariants, explicit mappings and unlabelled classification. For the broader counting taxonomy, use Number of Graphs MCQs: 10 Solved Questions on Simple, Undirected, Labeled and Unlabeled Graphs; it owns labelled graph totals, cycle enumeration, structured edge counts and the three-vertex class count that also appears in Q9. Here that count sits inside a progression on detecting isomorphism and classifying small graphs by preserved invariants.

7. The short version and next step

Reject with invariants. Refine with cycles and neighbourhoods. Prove with a bijection. For counting questions, classify components and degree sequences before counting cases.

The GATE category gives the wider preparation context. GATE Guidance by Sanchit Sir covers the complete CS sequence, while Engineering Mathematics for GATE is the narrower mathematics option. Record which invariant you missed, then reattempt only those questions after a week.