02. Trees

Tree

Let $T$ be a tree then

$T$ is an acyclic connected graph

Link to original

Minimal Connected Graph

Let $G$ be a graph then

$G$ is a Minimal Connected Graph if

1. $G$ is connected
2. $G-e$ is not connected for all $e\in E(G)$

Note that it means every edge is required for connectivity

Link to original

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

Link to original

Uniqueness of a Path in a Tree lemma

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

$T$ contains unique $x-y$ path

Link to original

Neighbourhood of a Vertex

Let $G=(V,E)$ be a graph with $v\in V$ then

Neighbourhood of $v$ is

$$\Gamma (v)={\Gamma }_G(v)=\{w\in V:vw\in E\}$$

Link to original

Degree of a Vertex

Let $G=(V,E)$ be a graph with $v\in V$ then

Degree of vertex $v$ is

$$d(v)=d_G(v)=|\Gamma (v)|$$

Link to original

Leaf of Graph

Let $G$ be a graph then

$v$ is a leaf of $G$ if

$$d(v)=1$$

Link to original

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

Link to original

Number of Vertices of $G$

Let $G$ be a graph then

$$|G|\equiv v(G)\equiv |V(G)|$$

is the number of vertices of $G$

Link to original

Number of Edges of $G$

Let $G$ be a graph then

$$e(G)\equiv |E(G)|$$

is the number of edges of $G$

Link to original

Number of edges when Removing Vertex of Graph

Let $G$ be a graph with $v\in V(G)$ then

$$e(G-v)=e(G)-d(v)$$

Link to original

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

Link to original

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

Link to original

Spanning Subgraph

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

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

$$V(H)=V(G)$$

Link to original

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

Link to original

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)

Link to original

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

Link to original

Adding Edges to a Graph

Let $G$ be a graph
Let $e$ be a edge then

$G+e$ is the graph formed from $G$ and adding edge $e$

Notation

Suppose $G=(V,E)$ then

$$G+e=(V,E\cup \{e\})$$

where $e=xy$ for $x\ne y$ and $e\notin E(G)$

Link to original

Maximal Acyclic Graph

Let $G$ be acyclic graph then

$G$ is maximal acyclic if there does not exist $e$ such that $G+e$ is acyclic

Link to original

Relation between Maximal Acyclic and Trees

Let $G$ be a graph then

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

Link to original

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$

Link to original