DA2: Eulerian, semi-Eulerian and Hamiltonian graphs

Eulerian graph definition

a connected graph that has an Eulerian trail

Eulerian trail definition

a closed trail that includes every edge

semi-Eulerian graph definition

a graph that contains a trail that includes every EDGE but DOESN’T return to the starting point (so contains a TRAIL, not a CLOSED trail)

2 important theorems for Eulerian/semi-Eulerian graphs

1- a graph is only Eulerian if and only if all the vertices are connected to an even number of edges (if all vertices are even)

2- a connected graph is semi-Eulerian if and only if it has exactly two odd vertices (odd number of edges connected to the vertex)

important point about semi-Eulerian graphs

the trail will start at one odd vertex and end at the other

Hamiltonian graph definition

a connected graph with a Hamiltonian cycle

what’s another word for hamiltonian cycle

tour

Hamiltonian cycle / tour definition

a cycle which visits every vertex only once (must meet every vertex, edges can be missed)

semi-Hamiltonian graph definition

if the graph has a Hamiltonian PATH, not CYCLE- the path visits every vertex, but doesn’t return to the starting vertex

is it possible for a graph to be both Hamiltonian and Eulerian?

yes

state Ore’s theorem

if G is a simple connected graph with n vertices, where n ≥ 3, then if deg v + deg w ≥ n for every pair of vertices v and w then G is Hamiltonian

explain Ore’s theorem in human language

let’s say we have a simple connected graph called G, with a number of points/vertices (n). if the graph has 3 or more vertices, then if the (number of edges joining to vertex v) + (number of edges joining to vertex w) is greater than n, the graph is Hamiltonian.