Leo | Graph Theory | Spanning tree

Spanning tree

Go to previous page.

A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges.

Theorems:

G is connected if and only if G has a spanning tree.

Corllary: if $G$ has connected with $n$ vertices and $n-1$ edges, then G is a tree.

Proof:

Since G is connect, so G has a spanning tree T.

Then T has $n-1$ edges. But G has $n-1$ edges as well.

So G is a tree as well.

Suppose G has n vertices. If any 2 of 3 following conditions hold for G, then G is a tree.
- G is connected.
- G has no cycle.
- G has n-1 edges.

If $T$ is a spanning tree of $G$ and $e$ is an edge of $G$ not in $T$, then $T + e$ contains exactly one cycle C. If $e'$ is an edge of C, then $T + e - e'$ is a spanning tree.

Proof:

Let $e = uv$. Any cycle in $T + e$ must use e.

Since T has no cycle, such a cycle consists of e and a $u-v$ path in T.

Since there is a unique $uv$ path in T, there is exactly one cycle in $T+e$

Let $e'$ be an edge on $C$, then $e'$ is not a bridge.

So $T+e-e'$ is connected. Removing $e'$ destroy the only cycle in $T+e$.

Therefore $T+e-e'$ has no cycle and it is a tree.

(Alternatively, $T+e-e'$ has the same number of edges as T, so it is a tree)

No graph contains exactly 2 spanning tree.

If $T$ is a spanning tree of $G$ and $e$ is an edge of $T$, then $T_e$ has 2 components, say $H$ is one of them. If $e'$ is in the cut induced by $V(H)$ in G, then $T-e+e'$ is a spanning tree of $G$.

Bipartite characterization:

Theorem: G is bipartitle if and only if G does not contains an odd cycle.

Proof:

This theorem has a if and only if relationship, therefore we need to prove in both directions.

$\Rightarrow$

Suppose $G$ is bipartite with bipartition, say $A$ and $B$.

Let $C=v_1, v_2, \cdots, v_k, v_1$ be a cycle of odd length in $G$

WLOG, $v_1 \in A$, then $v_2 \in B$, $v_3 \in A, v_4 \in B, \cdots$

Since $k$ is odd, so $v_k \in A$, but $v_k-v_1$ is an edge and both $v_k, v_1 \in A$ that is contradiciton

Therefore $G$ does not contain an odd cycle.

$\Leftarrow$

Suppose $G$ is not bipartite, then there exist a non-bipartite component $H$.

Since $H$ is connected, it has a spanning tree $T$.

Since T is partite,, thus it has bipartition (A,B)

Since $H$ is not bipartite, it contains an edge that ions 2 vertices in $B$ (WLOG) s say that $e=uv$

Let $v_1,v_2,\cdots, v_k$ be the unique $u-v$ path in $T$ (v_1 = u, v_k = v)

Then $v_1 \in B, v_2\in A, v_3\in B, \cdots$

Since $v_k \in B$, $k$ is odd. Then $v_1.v_2.\cdots. v_k, v_1$ is a cycle of length k, which is odd.