Week 42: TAOCP 2.3.4 Basic Mathematical Properties of Trees (part 1)

Part 1 covers the first three subsections: free trees (graphs without cycles) and spanning trees, oriented trees and their link to directed graphs, and the infinity lemma about infinite trees with finite branching.

Time About 7 hours this week

Why it matters

This is the bridge between data-structure trees and graph theory. Spanning trees show up in networking, clustering and circuit design.

Before you start

2.3.1 to 2.3.3
1.2.1 Mathematical Induction

How to approach it

Draw lots of small graphs. Prove to yourself that a tree on n vertices has n - 1 edges. Read 2.3.4.1 to 2.3.4.3 carefully; the infinity lemma is short but subtle.

Exercises

Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.

Traps

Mixing up free trees (no root) and oriented trees (with a root and direction).