View source for 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 graph are denoted d1, d2, d3, ..., dn. Then the following statement is true:''

<math>
\sum_{i=0}^{n} d_i = 2a
</math>

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/13.pdf

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

=Flags=

{{GraphsFlag}}