ISI2025-MCS-PCB (CS) | Question: 5

Question

For a graph $G=(V, E)$ and a subset $X \subseteq V$ of the vertices, the induced subgraph $G[X]$ is defined as $G[X]=\left(X, E^{\prime}\right)$, where $E^{\prime}=\{u v \in E \mid u, v \in X\}$.
Suppose $G=(V, E)$ is a connected undirected graph on two or more vertices and $T=(V, F)$ is a spanning tree of $G$. Let $S \subset V$ be a non-empty proper subset of the vertices and define $A=\{u v \in E \mid u \in S, v \in V \backslash S\}$. Prove or disprove each of the following:

1. $A \cap F \neq \varnothing$.
2. If $G[S]$ has $s$ connected components and $G[V \backslash S]$ has $t$ connected components, then $A \cap F$ contains at least $s+t-1$ edges.
3. If $A \subseteq F$, then either $T[S]$ or $T[V \backslash S]$ is disconnected.