Graph Theory

Vertex

a single point where lines or curves start/end

ODD – has an odd # of edges attached to it

EVEN – has an even # of edges attached to it

Edge

a line or curve that starts/ends at vertices

Loop – a special edge that starts and ends and the same

vertex (they count twice when determining the type of

vertex)

Path

a route along the edges that starts at one vertex and ends at

another vertex

Circuit

a special path that begins at one vertex and ends at the

same vertex

Eulerian

a path or circuit that uses each edge of the graph exactly

once.

Hamiltonian

a path or circuit that uses each vertex of the graph

exactly once.

EULER’S THEOREM

A graph has an Eulerian circuit if and only if it is

connected, and all of its vertices are even.

A graph has an Eulerian path if and only if it is

connected and has either no odd vertices, or exactly 2

odd vertices

(if 2 odd vertices, then you must start at one and end at

the other)

EULERIZATION

Eulerization occurs when edges are added in order to

guarantee an Eulerian Circuit

You want to keep new edges to a minimum

Only allowed to add edges between vertices that already have

edges

GUIDELINES FOR EULERIZATION

Circle all odd vertices

Pair off each odd vertex with another odd vertex that is

close to it

For each pair, find the path with the fewest edges

connecting them and duplicate the edges along this path