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.

  • $\begingroup$ 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$. $\endgroup$ – Yai0Phah Mar 14 '16 at 19:08

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.