GATE CS 2004 Q81 — Graphs: Connectivity, Matching, Colouring

We can prove that $G_1 \cup G_2$ must contain a cycle using proof by contradiction:

1. Assume $G_1 \cup G_2$ has no cycles.
2. Since $G_1$ is a connected spanning subgraph of $G_1 \cup G_2$, the graph $G_1 \cup G_2$ must also be connected.
3. A connected graph with no cycles is a tree. Thus, $G_1 \cup G_2$ is a tree.
4. Any connected spanning subgraph of a tree $T$ must be the tree $T$ itself. Since $G_1$ and $G_2$ are connected spanning subgraphs of $G_1 \cup G_2$, we must have: $$G_1 = G_1 \cup G_2 \quad \text{and} \quad G_2 = G_1 \cup G_2$$ This implies $G_1 = G_2$.
5. If $G_1 = G_2$, then their intersection is $G_1 \cap G_2 = G_1$, which is connected. This directly contradicts the given condition that $G_1 \cap G_2$ is not connected.

Therefore, our assumption is false, and $G_1 \cup G_2$ must have a cycle.