# 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.

## 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})