Let $G=(V,E)$ be an undirected graph with no simple cycles in it.
Let $G_i=(V_i,E_i) (i=1,2,3)$ be two sub-graphs of G, such that $G_i$ is a tree.
There are no $i,j$ such that $V_i \cap V_j=\emptyset$
Prove that $V_1\cap V_2 \cap V_3\neq \emptyset$
I have been sitting on this one for a while but I haven't managed to prove this.
I tried to assume that the intersection is empty, but wasn't able to reach anything.
I have noticed that $G_1\cup G_2\cup G_3$ is a tree, but couldn't make something out of it as well.
Can someone help out?
If for any $i,j, V_i \subseteq V_j$ the proof is clear and straightforward. Let it not to be this way.
Since $V_1 \cap V_2 \neq \emptyset$, hence there is a common vertex between two sets. We also know $V_3 \cap V_2 \neq \emptyset$ and $V_1 \cap V_3 \neq \emptyset$.
Now you need to prove $V_3$ must contain the common vertex of $V_1$ and $V_2$. Prove it by contradiction. Suppose it is not so. If $G_3$ has a vertex from $G_1$, say $v$ and $v \notin V_2$, and a vertex from $G_2$, say $u$ and $u \notin V_1$, it makes a path between $v$ and $u$ ($u \leftrightsquigarrow v$) because $G_3$ is a tree, and because $G_1 \cup G_2$ is also a tree (it is not jungle because they have common vertex), it means there is exactly a path between $u$ and $v$ in $G_1 \cup G_2$ as well which is different with the path $u \leftrightsquigarrow v$ in $G_3$. Hence $G_1 \cup G_2 \cup G_3$ must create a cycle which contradicting the fact that $G$ has no cycle. $\blacksquare$