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: $tex_8b33ec76ae3a9520de7d175e47ea8da5 Teaching Kids Programming - Math Proof of the Number of Odd Degree Vertices in a Graph is Even$ .

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.

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

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

Let’s assume there are N vertices, and the first $tex_02f4c130a05a4c170e643aa09a7dba7d Teaching Kids Programming - Math Proof of the Number of Odd Degree Vertices in a Graph is Even$ vertices are even degrees, and the $tex_b113b5a7a8595f5bf10e67b1e7a5a963 Teaching Kids Programming - Math Proof of the Number of Odd Degree Vertices in a Graph is Even$ vertices are odd degrees.

So we have:

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

The LHS is even as we have proved above, and the first item of the RHS is even because the first $tex_02f4c130a05a4c170e643aa09a7dba7d Teaching Kids Programming - Math Proof of the Number of Odd Degree Vertices in a Graph is Even$ 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:

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

is even. As the $tex_449c4dfd50f51f57e4e5dc022ee59098 Teaching Kids Programming - Math Proof of the Number of Odd Degree Vertices in a Graph is Even$ where $tex_828cc438e8789de6f4fff2ff3ca0918a Teaching Kids Programming - Math Proof of the Number of Odd Degree Vertices in a Graph is Even$ is from $tex_7a648db5068a07d177064beea742c1f0 Teaching Kids Programming - Math Proof of the Number of Odd Degree Vertices in a Graph is Even$ to $tex_07baee26b11d17fadc32609a4e1b0565 Teaching Kids Programming - Math Proof of the Number of Odd Degree Vertices in a Graph is Even$ is odd, then it must be multipled by an even number which is the number of the odd degree vertices.