Section 11.3 – Graph Theory

Graph – a diagram that shows analysis of a problem

Vertices – points on a graph

Edges – segments or curves linking the vertices (paths)

Euler path – a continuous path that travels along each edge only once.

		See example from pg. 712 in text.
	B

Degree – the number of edges at each vertex

Even vertices – a vertex with an even degree

Odd vertices – a vertex with an odd degree

Theorem

A graph contains an Euler path if and only if there is at most two odd vertices

See page 715 in text for even/odd diagrams

Euler circuit – an Euler path that starts and ends at the same vertex.

An Euler path that contains only even vertices