Degree Sequences and Graph Isomorphism for GATE: Handshake Lemma and Havel-Hakimi Drills

Degree-sequence questions look like small counting exercises until the options force two different decisions. Can this sequence belong to a simple graph, and do two drawings represent the same graph under different labels?

The first decision uses the Handshake Lemma and Havel-Hakimi. The second uses structural invariants and, when required, an adjacency-preserving mapping. Keep those jobs separate and the common traps disappear.

1. The Handshake Lemma

In any undirected graph, the sum of all vertex degrees is twice the number of edges:

sum deg(v) = 2E

Every edge contributes one to the degree of each endpoint, so it contributes two to the total. The degree sum must therefore be even.

This also proves that the number of odd-degree vertices is even. The sum of an odd number of odd integers is odd, but the total degree sum cannot be odd. A claimed graph with exactly three odd-degree vertices is impossible without any drawing.

For a worked count, suppose all six vertices have degree three. Then:

sum deg(v) = 6 x 3 = 18

2E = 18, so E = 18 / 2 = 9

Check the arithmetic in reverse: nine edges contribute 9 x 2 = 18 degree incidences. The count is consistent.

The lemma is necessary, not sufficient. An even sum does not guarantee that a simple graph can realise the sequence. It only tells you that the sequence has passed the first filter.

2. Degree sequences and the graphical question

A degree sequence lists all vertex degrees in non-increasing order. A sequence is graphical if at least one simple undirected graph has exactly those degrees.

Run two quick checks before doing anything longer:

1. The degree sum must be even.

2. On n vertices, no degree can exceed n - 1 because a simple graph has no self-loop and no repeated edge.

For example, (5, 2, 2, 1) cannot be the degree sequence of a simple graph on four vertices because five exceeds 4 - 1 = 3. The sequence (3, 3, 1, 1, 1, 1) has sum 10 and maximum 3, so it passes both quick checks. That still does not settle whether it is graphical.

Remove 3 and reduce the next three entries:

(3, 3, 1, 1, 1, 1) -> (2, 0, 0, 1, 1) -> sort -> (2, 1, 1, 0, 0)

Remove 2 and reduce the next two entries:

(2, 1, 1, 0, 0) -> (0, 0, 0, 0)

All entries are zero, so this sequence is graphical. The reduction also shows why an even degree sum is only a preliminary check: Havel-Hakimi supplies the decisive construction test.

Havel-Hakimi supplies the full decision procedure. Its logic is constructive: connect a highest-degree vertex to the vertices with the next highest remaining degrees, then ask whether the reduced problem can be realised. If d exceeds the number of remaining entries, the sequence is not graphical.

3. Havel-Hakimi worked on (4, 4, 3, 3, 2, 2)

The algorithm repeats four actions: sort, remove the first degree d, subtract one from the next d degrees, and sort again. A negative entry means not graphical. Reaching all zeros means graphical.

Start with:

(4, 4, 3, 3, 2, 2)

The sum is 4 + 4 + 3 + 3 + 2 + 2 = 18, which is even. There are six vertices and the maximum degree is 4 <= 5, so both preliminary checks pass.

Remove the first 4. Subtract one from the next four entries (4, 3, 3, 2), leaving the final 2 untouched:

(3, 2, 2, 1, 2) -> sort -> (3, 2, 2, 2, 1)

Remove 3 and reduce the next three entries:

(2, 2, 2, 1) -> (1, 1, 1, 1)

Remove 1 and reduce the next entry:

(1, 1, 1) -> (0, 1, 1) -> sort -> (1, 1, 0)

Remove 1 and reduce the next entry:

(1, 0) -> (0, 0)

All entries are zero, so the original sequence is graphical.

We can check the result by constructing one graph. Name the vertices A, B, C, D, E, F and use edges AB, AC, AD, AE, BC, BD, BF, CD, EF. The degrees are:

• A: 4 through B, C, D, E

• B: 4 through A, C, D, F

• C: 3 through A, B, D

• D: 3 through A, B, C

• E: 2 through A, F

• F: 2 through B, E

There are nine listed edges, matching 18 / 2 = 9. Both the reduction and an explicit realisation confirm the answer. The most common procedural error is failing to re-sort after a subtraction.

4. Graph isomorphism and its invariants

Two graphs are isomorphic if a one-to-one relabelling of vertices preserves adjacency exactly. If vertex u is adjacent to v in the first graph, their mapped vertices must be adjacent in the second, and non-adjacencies must also be preserved.

Isomorphic graphs must share every structural invariant. Useful GATE checks include:

• the same number of vertices and edges

• the same degree sequence

• the same number of connected components

• the same cycle counts for each length

• the same bridge and cut-vertex structure

• the same bipartite or non-bipartite status

One mismatch proves that two graphs are not isomorphic. Matching values do not, by themselves, prove that they are isomorphic. To prove isomorphism, provide or identify a vertex mapping that preserves the full adjacency relation.

This topic builds directly on cycle and connectivity language covered in Graph Theory: Euler and Hamiltonian Paths, Coloring and Connectivity.

5. Worked counterexample: equal degree sequence, not isomorphic

Compare K_(3,3) with the triangular prism. Both have six vertices, every vertex has degree three, and both therefore have degree sequence (3, 3, 3, 3, 3, 3).

The Handshake Lemma gives nine edges for either graph. In K_(3,3), each of the three vertices on one side joins all three on the other side, giving 3 x 3 = 9 edges. In the prism, the two triangles contribute three edges each and the three matching edges join corresponding corners, giving 3 + 3 + 3 = 9.

Still, the graphs are not isomorphic. The triangular prism contains two 3-cycles. K_(3,3) is bipartite, so every cycle in it has even length and it contains no triangle. Triangle count, equivalently the presence of a 3-cycle here, distinguishes them.

This example gives the key discipline: use degree sequence as a fast rejection test, never as automatic proof of isomorphism.

6. The traps GATE builds these on

• Accepting a sequence merely because its sum is even.

• Allowing a degree greater than n - 1 in a simple graph.

• Forgetting to re-sort after each Havel-Hakimi reduction.

• Stopping before the sequence reaches all zeros or produces an invalid entry.

• Declaring two graphs isomorphic because their degree sequences match.

• Comparing drawings by visual shape instead of adjacency.

Planarity is another invariant that can separate graphs, but it needs its own tools.

7. How GATE tests this and the official pointer

Expect a direct edge count from degrees, a graphical-sequence decision, an intermediate Havel-Hakimi state, or a pair of graphs that must be separated by an invariant. An MSQ can combine several true conditions, so test each statement independently.

These questions sit in the graph-theory portion of Discrete Mathematics. The current official GATE portal defines the cycle's syllabus and paper information, while the GATE category places the topic inside a broader preparation path. Use the official syllabus to confirm coverage; past-paper trends can guide revision, but they do not guarantee a fixed subject-wise mark share.

KnowledgeGate's practice bank has more than 1,300 Discrete Mathematics questions, which is enough to practise the procedure across many graph forms. The goal is not to remember one sequence. It is to execute the same checks accurately on a new one.

8. The short version and your next step

Use sum deg(v) = 2E for edge counts and parity checks. Use Havel-Hakimi to decide whether a sequence is graphical, sorting after every reduction. Use invariants to disprove isomorphism, but require a valid adjacency-preserving mapping to prove it.

Work the six-vertex sequence again without looking, then compare K_(3,3) and the prism from memory. Use the Engineering Mathematics course for the theory and the GATE Test Series for timed drills.