1
$\begingroup$

Let $T, C$ be a spanning tree and cycle in some graph $G$, respectively. Suppose $AB$ is an edge of $C$ and $T.$ Show that there is at least one other edge $UV \in C$ that can replace $AB \in T$ so that the resulting subgraph $T - AB + UV$ is still a spanning tree.

To start $T - AB$ is a two-component forest. If $C$ has no edge that can connect these components into a spanning tree in $G$, then $C$ must be disconnected in $G.$ Thus $T$ is not a spanning tree.

Not sure if it works. Would be happy if someone commented on it. Thanks.

$\endgroup$
1
$\begingroup$

Not really sure where you're making the leap that $C$ must be disconnected in $G$, or why it's necessary.

The result pretty much follows by definition (if you're using the fairly standard Wilson text). A subgraph $T$ of a connected graph $G$ is a spanning tree if and only if each circuit of $G$ has an edge removed such that the graph stays connected.

So if $T$ is a spanning tree, then the circuit $C$ must have an edge $UV$ removed by hypothesis. Replacing $AB$ with $UV$ gives us a new spanning tree $T-AB+UV$.

EDIT 1: Turns out I was wrong in my initial conjecture that any such $UV$ would work. We need to be more careful. Here's what we need to do:

First, you want to verify your hint (if you want/need to) that $T-AB$ has two components $T_A$ and $T_B$ containing $A$ and $B$, respectively. This can easily be done by repeated use of Wilson Theorem 9A which states that a tree is equivalent with the property that "any two vertices of $T$ are connected by exactly one path".

Next, we identify the specific edge $UV \in C-T$ that we want, which turns out to be some $UV \in T$ such that $U$ and $V$ are in different components (we can then assume without loss of generality that $U \in T_A$ and $V \in T_B$). It is easy to figure why $T-AB+UV$ works once you build a new circuit $D$ (that isn't necessarily the same as $C$) in $G$ containing $AB$ and $UV$ that links $A$ to $U$ in $T_A$ and $B$ to $V$ in $T_B$.

So we would really want such a $UV \notin T$ to exist. Denote the edges in $C$ as $C_0C_1, C_1C_2, \dots, C_{n-1}C_n$ for $n \geq 3$, where $C_{n-1}=A$ and $C_0 :=C_n :=B$. Note that $C_n$ is not in $T_A$ by definition. Let $m=min\{ 1 \leq i \leq n \colon C_i \notin T_A \}$. We find $C_{m-1}C_m$ necessarily follows our needed criteria.

EDIT 2: D41 follows directly from the last problem (since some $UV$ that follows our criteria exists for each $AB$ and $UV \notin T$ is hypothesized to be unique).

$\endgroup$
  • 1
    $\begingroup$ Context for this problem: imgur.com/DnxfxNV Given the hint(problem D40), how would you proceed with this problem? Also, for D41, can we say that $UV$ is the only edge that can replace an edge in $T$ where $T$ remains a spanning tree because if we replace an edge in $T$ with another edge in $T$ (which is also in C), then $T$ gets disconnected? Thanks. $\endgroup$ – user460345 Jul 23 '17 at 19:31
  • $\begingroup$ See the edit. to answer your first concern on how to utilize your hint (it turns out my initial conjecture was wrong and you need to use your hint). D41 answer coming in a second edit. $\endgroup$ – Dark Logician Jul 24 '17 at 17:58
  • $\begingroup$ To answer your second question, see EDIT 2. $\endgroup$ – Dark Logician Jul 25 '17 at 6:29

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.