Cedarville University

http://www.cedarville.edu/includes/htm/v6/afterbodystarttag.htm

Inspiring Greatness
Cedarville University
Like us on Facebook Follow us on Twitter Visit our Youtube channel

Chapter 5 - The Circuit Comes to Town
Euler's Theorems
 
·
We now want to look at three theorems proven by Euler which solve the Königsberg Bridge Problem.

 

Euler's Theorem 1

·
If a graph has any vertices of odd degree, then it cannot have an Euler circuit.

 
 
·
If a graph is connected and every vertex has even degree, then it has at least one Euler circuit.

 
 

Euler's Theorem 2

·
If a graph has more than two vertices of odd degree, then it cannot have an Euler path.

 
 
·
If a graph is connected and has exactly two vertices of odd degree, then it has at least one Euler path. Any such path must start at one of the vertices of odd degree and end at the other.

 
 

Euler's Theorem 3

·
The sum of the degrees of all the vertices of a graph is an even number. Actually, the sum of the degrees is 2 times the number of edges.

 
 
·
In every graph, the number of vertices of odd degree must be even.
File translated from TEX by TTH, version 0.9.

Next page in this chapter
Chapter 5 Home
I2M Home