a WALK on a graph is a sequence of vertex, edge, vertex, edge, ... , vertex where each edge joins the vertices surrounding it.
LENGTH OF A WALK is the number of edges.
a CLOSED WALK has first and last vertex as the same (OPEN WALK when they are different)
a PATH is a walk in which every vertex is distinct
TRAIL is a walk that never repeats an edge (can repeat vertices not edges)
CIRCUIT is a closed trail (can repeat vertices but not edges)
CYCLE is a circuit with only the first and last vertex equal (no repeated vertices or edges other than start and stop point).
EULERIAN CIRCUIT is a circuit that contains every vertex and every edge.
a graph is CONNECTED when there is a walk between any two vertices
EULERIAN TRAIL is a trail that visits every edge and every vertex (but start and stop at different points)
HAMILTONIAN CYCLE is a cycle that hits every vertex
a graph that contains a hamiltonian cycle is called HAMILTONIAN, a graph that contains an eulerian circuit is called EULERIAN
for fun think about a RANDOM WALK
Useful facts
A graph is Eulerian if and only if it is connected and every vertex is even. (I would like to prove this to you.)
A graph has an Eulerian trail (between two distinct vertices \(u\) and \(v\)) if and only if it is connected and all vertices except \(u\) and \(v\) are even.
Any cycle inside of a graph has no sub-cycles
Any cycle inside of a graph uses exactly two edges from each of the vertices of that cycle.
Find a connected graph with as few vertices as possible that has precisely two vertices of even degree.
Prove that a graph is bipartite if and only if it contains no odd cycles
Take two Eulerian graphs that share no vertices and connect them with a single edge. Is the resulting graph Eulerian? Does the resulting graph contain an Eulerian trail?
For any distinct vertices, \(u\) and \(v\) in a graph, prove that there is a walk between \(u\) and \(v\) if and only if there is a path from \(u\) to \(v\)
Is the following graph Eulerian? If so find an Eulerian circuit.
Here is a five room house, try to draw any continuous line that crosses every wall exactly one time. What can you prove and how? Here is a sample line:
