Discussion 2B

1 Touring Hypercube



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:

Because of the recursive nature of how hypercubes are constructed, proofs by induction are very powerful for hypercubes.

2 Trees

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

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.