More Graph Theory

Videos (~10 mins)

Please review:

Euler Paths and the 7 Bridges of Konigsberg (6:23)

Reading (~30 mins)

Please review:

DMOI 4.1

Warmup

Problem 1

A walk between vertex \(u\) and vertex \(v\) in a graph \(G\) is a sequence of vertices such that every subsequent pair of vertices in the sequence has an edge between them in \(G\). A path is a walk in which no vertices are repeated. A tree is a graph with the property that there is exactly one path between any pair of nodes in the graph.

Vertices of degree 1 are sometimes called leaves.

Here is a fact about trees, which you may use without proof:

Theorem 1 (Trees Have Leaves) Every tree has at least one vertex of degree 1.

Using Theorem 1, prove the following theorem:

Theorem 2 Any tree with \(n\geq 1\) vertices has exactly \(n-1\) edges.

Hints

Induction on \(n\), the number of nodes.
For the inductive step, it is necessary to start with a larger tree and “prune” it (rather than starting with a smaller tree and adding a node and an edge).
If you remove a leaf of a tree, is the result a tree? How do you know?

Problem 2

For each of the items 1. through 4. below, draw a \(G\) with at least \(5\) nodes that matches the given specifications. If it is not possible to match a specification, then explain why.

For each part, please do not include any nodes of degree 0 or 1 in your solution.

\(G\) has an Euler path and an Euler circuit.
\(G\) has an Euler path but not an Euler circuit.
\(G\) has an Euler circuit but not an Euler path.
\(G\) has neither an Euler path nor an Euler circuit.