Teaching Kids Programming – Math Proof of the Number of Odd Degree Vertices in a Graph is Even

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a Undirected Graph, we have that: the Number of Odd Degree Vertices in a Graph is Even.

Graph G is a collection of Vertices and Edges thus: .

As each edge contributes to Degree of Two (it is connected by two vertices). Thus the sum of all degrees is twice the number of edges.

Thus, we know the sum of all degrees is an even number.

Let’s assume there are N vertices, and the first vertices are even degrees, and the vertices are odd degrees.

So we have:

The LHS is even as we have proved above, and the first item of the RHS is even because the first vertices are even degrees. The second item must be even, because an even number (LHS) minus an even number (first item of RHS) is even, thus:

is even. As the where is from to is odd, then it must be multipled by an even number which is the number of the odd degree vertices.

Thus: we have proved that: The Number of Odd Degree Vertices in a Graph is an Even Number.

–EOF (The Ultimate Computing & Technology Blog) —