Indirect Proofs

Claim: If a graph G has an Euler circuit, then every vertex in G has even degree.

Proof: Suppose that G has a vertex v with odd degree. Let π be any circuit in G. If π does not visit v, then π is not an Euler circuit since it misses all edges of the edges incident on v. (Since v has odd degree, there is at least one edge incident on v.) Let k be the number of times that v appears on the circuit π. Each time that π visits v, it must enter v using an edge and leave v using a different edge. If any of these edges are repeated, then π is not an Euler circuit. Thus, π uses exactly 2k edges incident on v. Since 2k is an even number and v has odd degree, π must miss at least one edge incident on v. Thus, π is not an Euler circuit and G does not have any Euler circuits.

QED

Using an indirect proof allows us to assume the existence of a vertex v with odd degree. We can then use this "fact" to conclude that none of the circuits in G are Euler circuits.

Note: the proof above assumes that v does not have any self-loops (that is, an edge from v to itself). As discussed in class, self-loops are inconsequential since a graph has an Euler circuit if and only if the graph with all self-loops removed has an Euler circuit.