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) —
loading...
Last Post: Teaching Kids Programming - Conditions That A Connected Graph Can Be Drawn With One Stroke (Euler Path/Euler Cycle/Circuit)
Next Post: Teaching Kids Programming - Faulty Keyboard with an Inverse Key (Two Algorithms/Double-ended Queue)
