DMAT_L17

How to grow trees

ref

Theorem 1(Theorem).

Every tree with at least $2$ nodes has at least $2$ nodes of degree $1$.

The tree growing procedure:

1. Start with a single node.
2. Repeat any number of times: If you have a graph $G$, create a new node and connect it by a new edge to any node of $G$.

Theorem 2(Theorem).

Every graph obtained from the tree growing procedure is a tree, and every tree can be obtained in this way.

Theorem 3(Theorem).

Every tree on $n$ nodes has $n-1$ edges.

The proof of this supplied in the reference exemplifies the use of the template for proof by induction on number of vertices from the previous lecture.

---

Linear algebraic methods in combinatorics

A town has 32 residents, any two clubs have an even number of residents in common, and any cub has an of number of residents. Show that the town cannot have 33 clubs.