Connected components of a tree after removing edges of two subtrees

52 Views Asked by At

Let $F$ be a forest. Let $F_1$ and $F_2$ be a vertices disjoint trees ($V(F_1)\cap V(F_2) = \emptyset$) such that $F_1$ and $F_2$ are subgraphs of $F$.

If $F_1$ and $F_2$ are contained in the same connected component of $F$, then let $a \in V(F_1)$ and $b \in V(F_2)$ the ends of the shortest path of $V(F_1)$ to $V(F_2)$. Else get $a \in V(F_1)$ and $b \in V(F_2)$ (arbitraries vertices).

Let $F'$ be a any forest with $V(F') = V(F_1) \cup V(F_2)$ such that $a$ and $b$ belongs the differents connected components. How can I show that for each vertices pair $\{u,v\} \neq \{a,b\}$ in $V(F')$, we have that $u$ and $v$ are in differents connected components in $F-E(F_1)-E(F_2)$?

Follows the my reasoning: I know that since $F_1$ is a tree, then for each vertices pair in $V(F_1)$, we have that exists exactly one path connecting the vertices pair. Since $F$ is a forest, each vertices pair in $V(F_1)$ are in differents connected components in $F-E(F_1)$. Similarly, we obtain that each vertices pair in $V(F_2)$ are in differents connected components in $F-E(F_2)$. How can I to end the argument?

1

There are 1 best solutions below

2
On BEST ANSWER

Hints.

  1. If $P$ is the shortest path connecting $a$ and $b$ in $F$, then none of its vertices lies in $V(F')$ except $a,b$.

  2. Consider the case $u\in V(F_1)$, $v\in V(F_2)$ and $u\neq a$, $v\neq b$. If in $F$ there exists a path $Q$ from $u$ to $v$, then $V(P)\cap V(Q)=\varnothing$, so $F$ has cycle $P+Q$.

  3. The cases $u=a$, $v\neq b$ and $u\neq a$, $v=b$ are similar.