3
$\begingroup$

I'm trying to understand a proof from the book "Graph Theory with Application to Engineering & Computer Science" by Narsingh Deo.

The chapter is about trees in non oriented graphs.

A bit of terminology so that you can understand the theorem and the beginning of the proof from the book:

The author calls minimum spanning trees, shortest spanning trees.

The author calls a branch of a spanning tree any edge of the tree.

A chord of a spanning tree is any edge of the underlying graph that is not in the tree.

A fundamental circuit associated to a spanning tree is a circuit formed by adding one of its chords to a spanning tree (for the author a "circuit" is a closed path, there is no repetition of vertices, it's what most other sources I've read call a cycle). So, a fundamental circuit associated to a spanning tree is a actually a cycle formed by adding one of its chords to a spanning tree.

The distance between two spanning trees $S$ and $T$ of the same graph is (regarding $S$ and $T$ as sets of edges), is $|S\setminus T|$ (which happens to be equal to $|T\setminus S|$).

There's a step in the proof of Theorem 3-16 that I don't understand.

Theorem 3-16:

A spanning tree T (of a given weighted connected Graph G) is a shortest spanning tree (of G) if and only if there exists no other spanning tree (of G) at a distance of one from T whose weight is smaller than that of T

Proof:

Let $T_1$ be a spanning tree in G satisfying the hypothesis of the theorem (i.e. there is no spanning tree at a distance of one from $T_1$ which is shorter than $T_1$). The proof will be completed by showing that if $T_2$ is a shortest spanning tree (different from $T_1$) in G, the weight of $T_1$ will also be equal to that of $T_2$. Let $T_2$ be a shortest spanning tree in G. Clearly, $T_2$ must also satisfy the hypothesis of the theorem (otherwise there will be a spanning tree shorter than $T_2$ at a distance of one from $T_2$, violating the assumption that $T_2$ is shortest).

Consider an edge $e$ in $T_2$ which is not in $T_1$. Adding $e$ to $T_1$ forms a fundamental circuit with branches in $T_1$. Some, but not all, of the branches in $T_1$ that form the fundamental circuit with $e$ may also be in $T_2$; each of these branches in $T_1$ has a weight smaller than or equal to that of $e$, because of the assumption on $T_1$. Amongst all those edges in this circuit which are not in $T_2$ at least one, say $b_j$, must form some fundamental circuit (with respect to $T_2$) containing $e$.

I'm stuck at the last sentence I just quoted:

"Amongst all those edges in this circuit which are not in $T_2$ at least one, say $b_j$, must form some fundamental circuit (with respect to $T_2$) containing $e$."

I don't see why among those cycles, there should necessarily be one that contains $e$. Why is that?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

If we remove $e = (x,y)$ from $T_2$, then it breaks into two connected components, say $T_{2,x},T_{2,y}$. There is a unique path in $T_1$ from $x$ to $y$, which together with $e$ forms a fundamental cycle of $T_1$. The path starts at $T_{2,x}$ and ends at $T_{2,y}$, hence at some point it crosses between the two. Adding the corresponding edge to $T_2$ would result in a fundamental cycle containing $e$.

Improve this answer
$\endgroup$
10
  • $\begingroup$ I don't get it. The path you're talking about is a path in $T_1$. Why would there be an edge in that path, that, when added to $T_2$ would form, along with some other edges of $T_2$, a cycle containing $e$? $\endgroup$
    – DisplayName80
    Commented Oct 21, 2020 at 15:02
  • $\begingroup$ If I follow you, there's that edge, let's call it $f$, in $T_1$, that reconnects the two components of $T_2 \setminus \{e\}$. What proves that the fundamental cycle in $T_2$ associated to $f$ contains $e$ ? $\endgroup$
    – DisplayName80
    Commented Oct 21, 2020 at 15:48
  • $\begingroup$ I think I'm starting to understand. I'm going to try to detail the properties you're using. $\endgroup$
    – DisplayName80
    Commented Oct 21, 2020 at 16:09
  • $\begingroup$ If I remove $e = \{x, y\}$ from $T_2$, I get two connected components $T_{2, x}$, $T_{2, y}$ with $x \in T_{2, x}$ and $y \in T_{2, y}$. If I remove $e$ from the fundamental cycle it forms with edges of $T_1$, I get a path $P_1$ from $x$ to $y$ composed of edges of $T_1$. One of these edges must have one end in each component $T_{2, x}$, $T_{2, y}$ (because any path that starts in a set of vertices and ends in another set of vertices must contain an edge with one extremity in each set). I call that edge $f = \{x', y'\}$, with $x' \in T_{2, x}$ and $y' \in T_{2, y}$. $\endgroup$
    – DisplayName80
    Commented Oct 21, 2020 at 19:26
  • $\begingroup$ $f$ does not belong to $T_2$, otherwise, since $f$ connects $T_{2, x}$ and $T_{2, y}$, and since $f \neq e$, $T_2 \setminus \{e\}$ would be connected. $\endgroup$
    – DisplayName80
    Commented Oct 21, 2020 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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