1 Touring Hypercube
- Eulerian tour: a tour that traverses each edge exactly once
- Hamiltonian tour: a tour that traverses each vertex exactly once (except for start/end vertex)
- (It is easy to check whether a graph has an Eulerian tour, but there is no known fast algorithm to check whether a graph has a Hamiltonian tour)
A hypercube of degree has vertices, labeled by all -length bit strings. It is composed of two sub-hypercubes of degree , which are connected by edges. For an -dimensional hypercube:
- each vertex has degree
- there are edges
- you can assign -length bit string labels to the vertices such that adjacent vertices differ by exactly one bit
Because of the recursive nature of how hypercubes are constructed, proofs by induction are very powerful for hypercubes.
If a complete graph is the most connected a graph can be, a tree is the least connected a graph can be before being disconnected. A tree on vertices
- is connected
- has edges
- has no cycles
Proofs by induction on trees also work well because removing leaves of a tree gives you a tree.
Prove that all trees must have a leaf (a vertex with degree ).
Proof: Suppose there were no leaves. Then every vertex would have degree at least . From the previous discussion, we showed that if every vertex has degree at least , then there must be a cycle. This contradicts the fact that trees acyclic.
3 Edge Colorings
When dealing with edge colorings, it can be helpful to think of how many colors a vertex touches, and how this relates to the vertex’s degree.