First Theorem of Graph Theory

Notes

The first theorem of graph theory states:

Suppose a graph G has n vertices and a edges. Suppose the degrees of each of the N nodes are denoted $d_{1},d_{2},\dots ,d_{N}$.

Then the following statement is true:

$\sum _{i=0}^{n}d_{i}=2a$

The proof of this can be shown through the double counting argument. The left and right sides above both count the number of endpoints of edges. Summing up the degrees of each vertex counts up the number of ends of edges. Since each edge has two ends, we count each edge twice, and therefore the number of endpoints counted must be even.

A direct consequence of this is the following fact:

In any graph, the number of vertices of odd degree must be even.

This is a consequence of the equation given above: if a sum (sum of vertex degrees, left side of the equation) is even, there must be an even number of odd summands.

For a graph to be Eulerian, that is, for an Graphs/Euler Tour to exist on the graph, the number of vertices with odd degree must be 0 or 2.

Resources

Related Pages

Graphs/Euler Tour

Links

Course notes from Wayne Goddard at Clemson: https://people.cs.clemson.edu/~goddard/texts/discreteMath/

Also see: https://people.cs.clemson.edu/~goddard/