Questions: Degree Sequences and the Handshaking Lemma

Question 1

Someone proposes a graph with 6 vertices having degree sequence [4, 3, 3, 2, 2, 2]. Can such a graph exist?

• A. No — the maximum degree in any graph equals the number of vertices minus one, and degree 4 requires at least 5 vertices, so 6 is acceptable, but the sequence still fails another test
• B. No — the sum of degrees is 16, which is even, but it would require 8 edges, which exceeds what is possible
• C. Yes — the sum of degrees is 16 (even), so 16/2 = 8 edges would be required, and the two odd-degree vertices (both degree 3) number exactly 2, which is even
• D. No — the number of odd-degree vertices is 2, but the handshaking lemma requires zero odd-degree vertices

Answer: (C)

The Handshaking Lemma requires the sum of all degrees to be even (it must equal 2|E|). Sum here: 4+3+3+2+2+2 = 16 — even. So 8 edges would be needed. Additionally, the number of odd-degree vertices must be even: there are exactly 2 vertices of odd degree (both degree-3 vertices), which satisfies this requirement. The sequence passes both necessary conditions. (Passing these checks doesn't guarantee a graph exists — the Erdős–Gallai theorem gives the full characterization — but it doesn't immediately rule it out.)

Question 2

Why must every graph have an even number of vertices with odd degree?

• A. Because every vertex must connect to an even number of other vertices by graph construction rules
• B. Because the Handshaking Lemma guarantees the sum of all degrees is even, and a sum can be even only if the number of odd terms is even
• C. Because graphs with an odd number of odd-degree vertices would require a fractional number of edges
• D. Because the degree sequence must sum to a multiple of 4 for a valid graph

Answer: (B)

From the Handshaking Lemma: Σ deg(v) = 2|E|, which is always even. Now split the sum: degrees of odd-degree vertices contribute an odd amount each; degrees of even-degree vertices contribute an even amount each. The even-degree vertices' contributions sum to an even number. For the total sum to be even, the odd-degree vertices' contributions must also sum to an even number — and a sum of odd numbers is even only if there are an even count of them. Hence: number of odd-degree vertices is always even.

Question 3

It is possible to draw a graph in which exactly three vertices have odd degree.

• T. True
• F. False

Answer: False

The Handshaking Lemma guarantees the sum of all degrees equals 2|E|, which is even. If exactly three vertices had odd degree, those three odd numbers would sum to an odd number. Adding the even contributions from the remaining vertices still gives an odd total — contradicting Σ deg(v) = 2|E|. Therefore, no graph can have exactly 3 (or any odd number of) odd-degree vertices. This is a hard mathematical constraint, not just a convention.

Question 4

The Handshaking Lemma can be used to immediately rule out an impossible degree sequence: if the proposed degrees sum to an odd number, no graph with that degree sequence can exist.

• T. True
• F. False

Answer: True

Since Σ deg(v) = 2|E| must hold for any graph, the sum of degrees is always even. If someone proposes the degree sequence [3, 2, 2], the sum is 7 — odd — so no such graph exists. This is a necessary condition (failing it rules a sequence out), though not sufficient (a sequence with an even sum may still be unrealizable for other reasons, e.g., requiring more edges between two vertices than the graph allows). The Handshaking Lemma gives the quickest sanity check.

Question 5

Explain intuitively why the sum of all vertex degrees must equal twice the number of edges, using the idea of how each edge is 'counted' in the sum.

Model answer: Each edge connects exactly two vertices. When you sum up every vertex's degree, each edge gets counted once for the vertex at each of its two endpoints — so every edge contributes exactly 2 to the total sum. If there are |E| edges, the total is 2|E|. The handshake metaphor makes this vivid: each handshake (edge) involves two people (vertices), so the total number of 'hands shaken' (sum of degrees) is twice the number of handshakes (edges).

This double-counting argument is the simplest proof in graph theory. It works because the degree of a vertex counts incident edges from that vertex's perspective. When you aggregate across all vertices, each edge is seen from both its endpoints, so it contributes 2 to the total. This same double-counting technique appears throughout combinatorics: summing a quantity from different perspectives and equating the two counts is a recurring proof strategy.