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