Math 240 Discrete Mathematics - Counting Trees

Some Intro

Q: When are two graphs the same?

Illustration::

+--+      +--+      +--+              +--+     +--+    +--+
| a|+-----+ c+------+ b|              | a+-----+ b+----+ c|
+--+      +--+      +--+              +--+     +--+    +--+
  • Labelled: Every vertex has the same set of lable on its neighbour in both graphs

  • Unlabelled: Two graphs “look the same”, or some way to label both so thay are the same labelled graph.

Example

How many connected, labelled graphs with 3 vertices. Label: {0,1,2}

For a non-labelled linear graph, there are 3 ways to lable this.

For a labelled 3 nodes triangular graphs labelled clockwise from 0 to 2, there is 1 labelled graph and 2 Unlabelled gconnected graphs with 3 vertices.

Example 2: A path with n vertices

::

[ ]—–[ ]——-[ ]——–[ ]——[ ]

How many labelled graphs does this give? Labels: {0,1,…,n-1} (or {1,2,…n})

$ = {\{n!}\over {2}\} $ (reversing label order gives the same graph).

Tree

Definition

A tree is a connected graph with no cycle.

.. image::https://upload.wikimedia.org/wikipedia/commons/thumb/2/24/Tree\_graph.svg/180px-Tree\_graph.svg.png

Leaf

A leaf of a tree is a vertex in a tree that has degree 1

Proposition

Every tree has at least one leaf.

Every tree with (\geq 2) vertices has (\geq 2) leaves.

Proof

Let T be a tree with at least 2 vertices, let (v_1,v_2,\dots,v_k) be a maximum length path in the graph Since Path has maximum length, all neighbours of (v_i), (v_k) are on the path. But (v_1)‘s only neighbour on the path is (v_2), or else there is a cycle, and likewise, (v_k)‘s only neigbour on the path is (v_{k-1}) So (v_1), (v_k) are leaves.

Proposition

Any tree (T) with (n) vertices has (n-1) edges (for all (n\geq 1))

Proof

Use induction, (n=1) T pass Inductive step: let (n>1), fix a tree (T) with (n) vertices. Let (v) be a leaf of (T) let (w) be its neighbour. Remove (v) from (T) to get (T\prime) with (n-1) vertices. By induction (T\prime) has ((n-1)-1=n-2) edges, and adding back the edge {v,w} gives (n-1) edges.

Corollary

If (T=(V,E)), (|V|=n), then (\sum_{v \in V} deg(v) = 2n-2) by handshaking lemma.

Counting Trees

Unlabelled

::

+——+ +——–+ +——-+ +——-+ +————+ | n=1 | | n=2 | | n=3 | | n=4 | | n=5 | +——+ +——–+ +——-+ +——-+ +————+

                +-+         +-+         +-+                    +-+       +--+    +--+
+-+             +++         +++         +++                    +++       +-++    +-++
+-+              |           |           |                      |          |       |
                 |           |           |      +-+            +++         |       |
                +++         +++         +++     +++            +++         +-+-+---+
                +-+         +++         +++      |              |            | |
                             |           +       |             +++           +-+
                             |           |      +++            +++           | |+---+
                             |          +++     | |             |       +-+--+ ++   |
                            +++         +++     +-+-+          +++      +-+     +---+
                            +-+          |      |   |          | |
                                         |     +++ +++         +++
                                         |     +-+ +-+          |
                                       +-+                    +-++       +--+               +-+
                                       +-+                    |  |       +-++           +---+ |
                                                              +-++         +---+--+   +-++  +-+
                                                                |          +---+  +---+  +
                                                              +-++       +-++  +--+   +--+
                                                              +--+       +--+

Labelled

::

n=1                 1
n=2                 1
n=3                 3
n=4                 16

Cayley’s Theorem

The number of labelled trees with (n) vertices is (n^{n-2})

Proof idea: Efficient storage of trees

Adjacency matrix

= = = = = = + 1 2 3 4 5 1 0 0 0 1 0 2 0 0 1 1 0 3 0 1 0 0 0 4 1 1 0 0 1 5 0 0 0 1 0 = = = = = =