03 - Trees

Tree

Let $T$ be a tree then

$T$ is an acyclic connected graph

Equivalence of Tree and Minimal Connected Graph lemma

Let $G$ be a graph then

$G$ is a tree $⟺$ $G$ is a minimal connected graph

Proof

Suppose $T$ is a tree then $T$ is connected by definition
If $T-xy$ is connected where $xy\in E(T)$ then exists $x-y$ path

$$x=v_0{v}_1\cdots v_t\text{ in }T-xy$$

As $t\ge 2$ as $xy\notin T-xy$ then
$v_0{v}_1\cdots v_t$ forms cycle in $T$ contradicting $T$ being cyclic

Conversely suppose $T$ is a minimal connected graph

If $T$ contains cycle $v_1{v}_2\cdots v_t$ with edge $e=v_1{v}_t$ then
As $T$ is connected then exists $x-y$ path for $x,y\in V(T)$
If path uses $e$ then replace $e$ with

$$v_1{v}_2\cdots v_t\text{ or }{v}_t\cdots v_2{v}_1$$

Hence there is a $x-y$ walk in $T-e$ thus $T-e$ is connected
This contradicts $T$ being minimal connected so $T$ is acyclic and hence a tree

Uniqueness of a Path in a Tree lemma

Let $x$ and $y$ be vertices of tree $T$ then

$T$ contains unique $x-y$ path

Property of Tree with at least Two Vertices lemma

Let $T$ be a tree with at least two vertices then

$T$ has at least two leaves

Proof

Let $P=v_0{v}_1\cdots v_t$ be a longest path in $T$ (existence as $T$ is finite)

As $t\ge 1$ then $T$ has at least one edge

Suppose $v_0$ has neighbour $x\notin \{v_0,\cdots ,v_t\}$ then
$x{v}_0\cdots v_t$ would be a longer path which is a contradiction

Suppose $v_0$ has neighbour $v_i$ on $P$ where $i\ge 2$ then
$v_0\cdots v_i$ would form a cycle in $T$ which is a contradiction then

$v_0$ has exactly one neighbour which is $v_1$ so $v_0$ is a leaf
Similarly $v_t\ne v_0$ is a leaf

Removing Leaf from Tree lemma

Let $T$ be a tree with leaf $v$ then

$T-v$ is a tree

Proof

As $T$ is acyclic then any subgraph of $T$ is also acyclic so $T-v$ is acyclic

Let $x,y\in V(T-v)$
As $T$ is connected then exists $x$-$y$ path

$$x=v_0{v}_1\cdots v_t$$

As $v$ is not an endpoint of path as $x,y\ne v$ and
$v\ne v_i$ for $1\le i\le t-1$ as $v$ is a leaf (as it would have two distinct neighbours in $T$) then

$P$ is a path in $T-v$ so $T-v$ is connected
Hence $T-v$ is a tree

Number of Edges in a Tree lemma

Let $T$ be a tree with $|T|=n$ vertices then

$$e(T)=n-1$$

Proof

Induction on $n$ so
For $n=1$ then $T$ has no edges

Suppose $|T|=n\ge 2$ then $T$ has a leaf $v$

Hence

$$T-v\text{ is a tree with }n-1\text{ vertices}$$

Hence by induction then $T-v$ has $n-1$ edges
As one edge is removed then $T$ has $n-1$ edges

Spanning Tree

Let $G$ be a graph
Let $H$ be a subgraph of $G$ then

$H$ is a spanning tree of $G$ if $H$ is a spanning subgraph and a tree

Connected Graph contains Spanning Tree

Let $G$ be a connected graph then

$G$ contains at least one spanning tree

Note that this can be found by removing edges one at a time until it is connected (and so minimally connected)

Relation of Connectivity and Edges to a Tree lemma

Let $G$ be a graph where $|G|=n$ then

$G$ is a tree $⟺$

1. $G$ is connected

2. $e(G)=n-1$

Proof

If $G$ is a tree then

1. Connected by definition
2. $n-1$ edges by Number of edges in a tree

Suppose $G$ is connected and has spanning tree $T$
As $T$ is a tree with $n$ vertices then it has $n-1$ edges
Hence $T=G$

Thus $T$ is a subgraph with al vertices and all $n-1$ edges of $G$ hence $G$ is a tree

Relation between Maximal Acyclic and Trees

Let $G$ be a graph then

$G$ is a tree $⟺$ $G$ is maximal acyclic

Relation between Acyclic and Edges to Tree

Let $G$ be a graph with $n$ vertices then

$G$ is a tree $⟺$

1. $G$ is acyclic

2. $e(G)=n-1$