# Use kruskal's algorithm to show that if G is a connected graph, then any subgraph that contains no circuits is part of some spanning tree for G.

So this is the whole question.

Use Kruskal's algorithm to show that if G is a connected graph, then any (not necessarily connected) sub graph that contains no circuits is part of some spanning tree for G. Consider both the weighted and unweighted cases.

I know how to use Kruskal's algorithm to find minimum spanning trees, but this question is really throwing me off. I kind of understand what it is saying, and can visualize it, but I cannot really come to any conclusions on actually solving it. If G is a connected sub graph, and you use Kruskal's algorithm to solve for the minimum spanning tree, I see that you can get multiple sub graphs, but I do not see how that is answering the question. I am honestly very lost and confused on what to do.

• Hint: Given the graph $G=(V,E)$ and a subset $S\subseteq E$ without cycle. Consider the weight function $w=\chi_{E\setminus S}\colon E\to\mathbb\{0,1\}$ such that $w(e)=0$ for $e\in S$ and $w(e)=1$ for $e\in E\setminus S$. – Yai0Phah Mar 14 '16 at 19:08

## 1 Answer

Let $G$ be the connected graph (not necessarily cycle-free) consisting of vertices $V$ and edges $E = \{e_i\}$, and let $H$ be a cycle-free subgraph, consisting of vertices $U$ and edges $F= \{f_j\}$ (with $\{f_j\} \subseteq \{e_i\}$). Write $H = \bigcup_k H_k$ where each $H_k$ consists of the edges in a connected subgraph of $H$ and the $H_k$ are all disjoint. Let the subgraph with edges $H_k$ be labelled $F_k$.

Let $w_\max$ be the maximal weight over all the edges in $E$; if $G$ was a non-weighted graph, then arbitrarily assign weights $1$ to all edges in $G$ so that $w_\max$ is still meaningful. Label the weights of edge $e_i$ as $w_i$.

Now create weighted connected graph $G'$ with vertices $V$ and edges $E$, and weights $$w'(e_i) = \left\{ \begin{array}{cc} w(e_i) + w_\max + 1 & e_i \in F \\ w(e_i) & e_i \not\in F \end{array} \right.$$ Now select any vertex $u \in U$ and using Kruskal's algorithm, from a minimal spanning tree for $G'$. Then there is some unique $k$ for which $u \in H_k$. For any edge $x \not\in H_k$, if $x$ is touching a vertex in $H_k$ then $x$ cannot be in any other $H_{k'}$ with $k' \neq k$ (and in fact cannot even touch a vertex in $H_k'$) since all the $H_k$ are disjoint. So each edge within $H_k$ has lower weight (in $G'$) than any edge in $E - H_k$ that touches a vertex in $H_k$, as those edges cannot be part of $F$.

Since Kruskal's algorithm is "greedy", and all edges within $H_k$ have lower weight than any edge in $G' - H_k$ touching a vertex in $H_k$, the algorithm -- although it is being applied to the whole of $G'$ -- will determine a spanning tree of $H_k$ before including any vertex outside of $H_k$. Let the step number before the first step outside of $H_k$ be $s_1$. Thus the edges in the tree $T_{n_1}$ at step $n_1$ span the subgraph $H_k$.

Having left $F_k$, the ensuing steps in Kruskal's algorithm cannot revisit $H_k$, since that would form a cycle. So eventually the algorithm will land on a vertex in some $H_{k'}$ with $k'\neq k$. At that point, because the edges within $F_{k'}$ are all of olower withght than edges leaving $H_{k'}$, the algorithm adds an entire spanning tree of $H_{k'}$ to the existing tree.

The key point is that while it was always guaranteed that the eventual spanning tree would touch each vertex in $U_k$ (or $U_{k'}$0, one could imagine the tree using edges that were not part of the connected subgraph $F_k$ (or $F_{k'}$0, so that the subgraph $H$ would not be part of the spanning tree. But the greediness, combined with the choice of weights in $G'$, has ensured that every edge in $F_k$ is part of $T_{n_1}$, and every edge in $F_{k'}$ is part of $T_{n_2}$

Continue in this fashion until the next $H_{k''}$ is encountered, and so forth: When the algorithm terminates and the tree $T$ spans $G'$, it also includes all edges in $F$, and is therefore the subgraph $H$ is part of that spanning tree $T$.