Parity Consequences of the Handshake Lemma

Why Odd Degrees Come in Pairs

The Handshake Lemma says that when the degrees of all vertices are added, every edge contributes two incidences. Thus the degree sum is even. This simple fact has a useful consequence: a finite undirected graph cannot have an odd number of vertices of odd degree. Isolated vertices cause no exception, and loops cause no exception provided their contribution to degree is counted correctly.

We use finite undirected graphs. A graph may be simple, or it may be an undirected multigraph with parallel edges and loops. In a multigraph, parallel edges are counted separately. A loop has both of its incidences at the same vertex, so it contributes two to that vertex's degree. The graph with no vertices is allowed.

Definition: A vertex has even degree if its degree is divisible by \(2\), and odd degree otherwise. The odd-degree vertex set is \(\{v\in V(G):\deg(v)\text{ is odd}\}\).

For a graph with \(m\) edges, the Handshake Lemma is \(\sum_{v\in V(G)}\deg(v)=2m\). Here \(m\) counts edges with multiplicity, including loops. A loop contributes two to the degree sum, just as a non-loop edge contributes one at each of its two endpoints. We use this established counting result to derive the parity consequence.

The Parity Consequence

Theorem: Every finite undirected graph has an even number of odd-degree vertices. This holds for simple graphs and for multigraphs with loops, with a loop contributing two to the degree of its incident vertex.

Proof. Let \(G\) be a finite undirected graph with \(m\) edges. By the Handshake Lemma, \(\sum_{v\in V(G)}\deg(v)=2m\), which is even. In this sum, each even degree contributes \(0\) modulo \(2\), and each odd degree contributes \(1\) modulo \(2\). Therefore the sum modulo \(2\) is the number of odd-degree vertices modulo \(2\). Since the sum is even, that number is even. If \(V(G)=\varnothing\), the sum is the empty sum \(0\), and the odd-degree vertex set is empty, which also has even size. \(\square\)

The theorem constrains the number of odd-degree vertices, not which vertices have odd degree. The number may be \(0,2,4,\dots\), up to the order of the graph. In particular, a graph with exactly one odd-degree vertex is impossible. This is a necessary condition on any proposed degree list: if it contains an odd number of odd entries, it cannot be the list of degrees of a finite undirected graph.

Worked Example: A Simple Graph with an Isolated Vertex

Let \(G\) be the simple graph with \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,23,31,34,45\}\). Vertex \(6\) is isolated, meaning that it has no incident edges. Find the degrees and check the parity conclusion.

Count the edges incident with each vertex. Vertex \(1\) is incident with \(12\) and \(31\), so \(\deg(1)=2\). Vertex \(2\) is incident with \(12\) and \(23\), so \(\deg(2)=2\). Vertex \(3\) is incident with \(23,31,34\), so \(\deg(3)=3\). Vertex \(4\) is incident with \(34,45\), so \(\deg(4)=2\). Vertex \(5\) is incident with \(45\), so \(\deg(5)=1\). Vertex \(6\) has no incident edges, so \(\deg(6)=0\).

\sum_{v\in V(G)}\deg(v)=2+2+3+2+1+0=10=2\cdot5=2|E(G)|.

The odd-degree vertices are \(3\) and \(5\), so there are \(2\), an even number. Independently, the edge list contains five edges, and the degree sum computed above is \(10\), twice that edge count. The isolated vertex contributes degree \(0\); including it changes neither the degree sum nor the number of odd-degree vertices.

Loops and Parallel Edges

In a multigraph, degrees are counted by incidences, not merely by the number of distinct neighboring vertices. A loop has two incidences at its vertex. Parallel edges are counted individually, so two parallel edges from \(u\) to \(v\) contribute \(2\) to \(\deg(u)\) and \(2\) to \(\deg(v)\). These conventions ensure that each edge still contributes exactly two to the total degree sum.

Worked Example: Loops, Parallel Edges and an Isolated Vertex

Let \(G\) be an undirected multigraph with \(V(G)=\{u,v,w,z\}\). Its edge multiset consists of two loops at \(u\), two parallel edges joining \(u\) to \(v\), one edge \(vw\), and one loop at \(w\). Vertex \(z\) is isolated. List edges with multiplicity: \(E(G)=\{uu,uu,uv,uv,vw,ww\}\).

The two loops at \(u\) contribute \(2+2=4\) to \(\deg(u)\), and the two \(uv\) edges contribute \(1+1=2\). Thus \(\deg(u)=4+2=6\). Vertex \(v\) is incident with the two \(uv\) edges and the edge \(vw\), so \(\deg(v)=1+1+1=3\). Vertex \(w\) receives \(1\) from \(vw\) and \(2\) from its loop, so \(\deg(w)=1+2=3\). The isolated vertex has \(\deg(z)=0\).

\sum_{x\in V(G)}\deg(x)=6+3+3+0=12=2\cdot6=2|E(G)|.

The odd-degree vertices are \(v\) and \(w\), giving \(2\). As an independent check of the edge count, there are two loops at \(u\), two \(uv\) edges, one \(vw\) edge and one loop at \(w\), for \(2+2+1+1=6\) edges. Counting the two incidences of each gives \(2\cdot6=12\), matching the degree sum. The loop incidences and the parallel edges are both included.

A Subset Version of the Parity Rule

The same incidence count can be made for just a selected set of vertices. For a subset \(S\subseteq V(G)\), call an edge a boundary edge of \(S\) if it has one endpoint in \(S\) and one endpoint outside \(S\). A loop cannot be a boundary edge: both of its incidences are at its one vertex.

Proposition: For every vertex subset \(S\) in a finite undirected graph, the number of odd-degree vertices in \(S\) has the same parity as the number of boundary edges of \(S\). Parallel boundary edges are counted separately.

Proof. Let \(e(S)\) be the number of edges whose two endpoints lie in \(S\), counting multiplicity and including loops at vertices of \(S\). Let \(b(S)\) be the number of boundary edges, also counting multiplicity. When the degrees of vertices in \(S\) are added, each edge with both endpoints in \(S\) contributes two incidences, each boundary edge contributes one, and each edge with no endpoint in \(S\) contributes zero. A loop in \(S\) contributes its two incidences to the first count. Hence \(\sum_{v\in S}\deg(v)=2e(S)+b(S)\). Modulo \(2\), the term \(2e(S)\) is even, so the degree sum has the same parity as \(b(S)\). On the other hand, reducing the degree sum modulo \(2\) counts exactly the odd-degree vertices in \(S\), because each odd degree contributes \(1\) and each even degree contributes \(0\). The two counts therefore have the same parity. If \(S=\varnothing\), both counts are zero, so the statement also holds. \(\square\)

Worked Example: Checking a Vertex Subset

Let \(G\) be the simple graph with \(V(G)=\{a,b,c,d,e,f\}\) and \(E(G)=\{ab,ac,bc,cd,de,ef\}\). Take \(S=\{a,b,c,d\}\). Verify the subset parity rule by computing both sides.

First compute all degrees. Vertices \(a\) and \(b\) each have degree \(2\), from \(ab,ac\) at \(a\) and \(ab,bc\) at \(b\). Vertex \(c\) has degree \(3\), from \(ac,bc,cd\). Vertex \(d\) has degree \(2\), from \(cd,de\). Vertex \(e\) has degree \(2\), from \(de,ef\), and vertex \(f\) has degree \(1\), from \(ef\). Thus the odd-degree vertices are \(c\) and \(f\). Exactly one of these, \(c\), lies in \(S\).

The edges with both endpoints in \(S\) are \(ab,ac,bc,cd\), so \(e(S)=4\). The only edge with one endpoint in \(S\) and one outside is \(de\), so \(b(S)=1\). The degree sum over \(S\) is \(2+2+3+2=9\), and the incidence count gives \(2e(S)+b(S)=2\cdot4+1=9\). Both the number of odd-degree vertices in \(S\) and the number of boundary edges are odd.

Check: The whole graph has \(6\) edges, so the total degree sum is \(2\cdot6=12\). The computed degrees also sum to \(2+2+3+2+2+1=12\). Its two odd-degree vertices \(c,f\) agree with the main theorem, while the subset calculation explains why \(S\) contains an odd number of them: exactly one edge leaves \(S\).

Connected Components and Common Mistakes

A connected component is a maximal set of vertices in which every pair can be joined by a path. Applying the main theorem to each component shows that each component has an even number of odd-degree vertices. Indeed, all edges incident with a vertex of a component stay within that component, so its degree there is its degree in the whole graph. The theorem applies to that finite component, including a component consisting of a single isolated vertex; its sole degree is \(0\).

A common mistake with loops is to count a loop as one edge but also to count it as only one incidence in its vertex's degree. For example, take \(V(G)=\{x,y\}\) and \(E(G)=\{xx,xy\}\). The incorrect calculation \(\deg(x)=2,\deg(y)=1\) counts the loop only once in \(\deg(x)\). It gives degree sum \(2+1=3\), even though \(2|E(G)|=2\cdot2=4\). The correction is that \(xx\) contributes two to \(\deg(x)\), so \(\deg(x)=2+1=3\), while \(\deg(y)=1\). Now the degree sum is \(3+1=4\), and the two odd-degree vertices are \(x\) and \(y\).

Another useful check is to distinguish a statement about all vertices from one about a chosen subset. The whole graph always has an even number of odd-degree vertices. A subset \(S\), however, may contain an odd number; the subset proposition says that this happens exactly when an odd number of edges leave \(S\). The boundary count must include every parallel edge separately.

Check Your Understanding

Use the degree-sum argument and the stated incidence conventions in your answers.

Can a finite undirected graph have exactly three odd-degree vertices? Explain why or why not.
A vertex has two loops and three ordinary incident edges, each joining it to a different vertex. What is its degree?
For a vertex subset \(S\), suppose exactly four edges leave \(S\). What can you conclude about the number of odd-degree vertices in \(S\)?
Why does adding an isolated vertex not change the parity conclusion for the odd-degree vertex count?
In a multigraph, why must parallel boundary edges be counted separately in the subset parity rule?