How I can show that the swap of edges not change the original connectivity

Question

Let $G$ be a graph. We say that $u$ and $v$ are connected in $G$, if exists a path of $u$ to $v$ in $G$.

I wish show the following:

Let $F$ be a forest and $T_1$ a tree with $T_1 \subseteq F$ (subgraph of $F$). Let $T_2$ be a tree with $V(T_2) = V(T_1)$ (Note that $T_2$, not necessarly is equal to $T_1$). How can I show that $u$ and $v$ are connected in F if and only if $u$ and $v$ are connected in $(F-E(T_1)) \cup E(T_2)$?

I know that $V(T_2) = V(T_1)$ and difference of the graphs is the swap of $T_1$ by the $T_2$. This is sufficient to demonstration?

Answer 1

I believe the graph $T = T_1 \cap T_2$ which has vertex set $V = V(T_1) = V(T_2)$ and edge set $E = E(T_1) \cap E(T_2)$ is itself a tree. This is a general fact about intersections of subtrees of a tree.

In particular $T$ is connected and so contains a path from $u$ to $v$. To finish the proof observe the edges of $T$ are contained in your set $( F - E(T_1) ) \cup E(T_2)$.

Answer 2

This really has nothing to do with trees or forests, except that trees are connected.

If $G$ is a graph and $G_1$ is a connected subgraph of $G,$ then replacing $G_1$ with another connected graph $G_2$ on the same nodes as $G_1$ gives a resulting graoh $G'$ and $G'$ is connected if and only if $G$ is connected.

This follows almost immediately using a property of quotient graphs:

Lemma: If $G=(V,E)$ is a graph and $G_1=(V_1,E_1)$ is a connected subgraph. Then $G$ is connected if an only if $G/G_1$ is connected.

The quotient graph is the graph $G$ with all of the nodes of $G_1$ identified to one node.

The lemma gives the result since $G/G_1=G'/G_2.$ So $G$ is connected if and only if $G/G_1$ is connected, if and only if $G'/G_2$ is connected, if and only of $G'$ is connected.

---

Most of a proof of the lemma:

If $G$ is connected, we clearly see that $G/G_1$ is connected. Any path in $G$ becomes a path in $G/G_1.$ The path might be shorter.

Now assume $G/G_1$ is connected.

Given a $u,v\in G,$ if we have a path $v_0=\overline u,v_1,\dots,v_n=\overline v$ in $G/G_1.$ We can ensure that only one of the $v_i$ corresponds the single merged point.

Now, the edge $\{v_{i-1},v_i\}$ corresponds to some edge $\{v_{i-1},w_s\}$ in $G,$ with $w_s\in V_1.$ And the edge $\{v_i,v_{i+1}\}$ corresponds to an edge, $\{w_e,v_{i+1}\}$ in $G,$ for $w_e\in V_1.$ And since $G_1$ is connected, there is a path $w_s,w_1,w_2,\dots,w_k,w_e$ in $G_1,$ and hence in $G$. Then we have a path in $G$:

$$u=v_0,v_1,\dots,v_{i-1},w_s,w_1,w_2,\dots,w_k,w_e,v_{i+1},\dots,v_n=v.$$

This needs a slight adjustment when one or both of $u,v\in V_1,$ but those cases are even easier.

---

Generalization of Lemma

If $G=(V,E)$ is a graph, and $\sim$ is an equivalence relation on $V,$ we can define the quotient graph $G/\sim=(V/\sim,E')$ where $$E'=\{\{\overline u,\overline v\}\mid \{u,v\}\in E \land \overline u\neq\overline v\},$$ where $\overline w$ is the equivalence class of $w\in V.$

You easily get that if $G$ is connected, then so is $G/\sim,$ with no conditions on $\sim.$

To get the reverse, you need some conditions on $\sim.$

The more general result:

If $G=(V,E)$ is a graph with an equivalence relation $\sim$ such that if $u\sim v$ then there is a path $u_0=u,u_1,u_2,\dots,u_n=v$ in $G$ with $u_i\sim u_{i+1}$ and $\{u_i,u_{i+1}\}\in E,$ for $i=0,1,\dots,n-1.$

Then $G$ is connected if and only if $G/\sim$ is connected.

So, essentially, each equivalence class of nodes gives a path-connected sub-graph.