Handshake Lemma/Examples/Impossible Order 6 Graph

Examples of Use of Handshake Lemma

There exists no undirected graph whose vertices have degrees $2, 3, 3, 4, 4, 5$.

Proof

If such a graph were to exist, it would have exactly $3$ odd vertices.

This contradicts the Handshake Lemma, which states that the number of odd vertices is even.

$\blacksquare$

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex: Problem $2$