Here is a nice little problem in graph theory that was posed to me recently (by Swagato) -
A dominating set of an undirected graph is a set of vertices $U$ such that every vertex in $V - U$ has at least one neighbour in $U$. Now, in an undirected graph $G = (V,E)$ having minimum degree $d$, if $(V_1, V_2)$ be a cut of size less than $d$, then prove that every dominating set of $G$ has a non-null intersection with both $V_1$ and $V_2$. [Note: size of a cut = number of cross edges]
My proof follows -
Let $|V| = v$, $|V_1| = v_1$ and $|V_2| = v_2$.
Without loss of generality, we can assume that $v_1 \leq v_2$.
Also, its easy to see that we must have $v_1 > 1$, because otherwise, if we have $v_1 = 1$, then all the edges incident to the single vertex belonging to $V_1$ cross the cut $(V_1, V_2)$. The minimum degree of the graph $G$ being $d$, there has to be at least $d$ edges incident to this solitary vertex belonging to $V_1$, which in turn implies that there has to be at least $d$ edges crossing the cut. However, this directly contradicts the fact that the cut $(V_1, V_2)$ has size less than $d$.
Now, since the graph $G$ has minimum degree $d$, each vertex $u \in V_1$ must have at least $d$ edges incident to it, out of which a maximum of $v_1-1$ edges can have a vertex also belonging to $V_1$ as its other endpoint. Thus, each vertex $u \in V_1$ must contribute at least $d-(v_1-1)$ cross edges to the cut $(V_1, V_2)$, which means that the size of the cut has to be at least $v_1.(d-(v_1-1))$. However, we already know that the size of the cut is strictly less than $d$. Combining the above two facts, we get:
$
\begin{align}
v_1.(d-(v_1-1)) < d &\implies d.(v_1-1) < v_1.(v_1-1) \\\\
&\implies d < v_1 \hspace{44mm} \hbox{[ since $v_1 > 1$ ]}
\end{align}
$
This implies that the size of the cut has to be strictly less than $v_1$.
Let $U$ be any dominating set in the graph $G$.
If possible, let us assume that $U \cap V_1 = \emptyset$, which implies that $U \subseteq V_2$. Going by the definition of dominating set, each vertex $u \in V_1$ must be adjacent to at least one vertex belonging to $U$. Since $U \subseteq V_2$, this implies that each vertex $u \in V_1$ must be contributing at least one cross edge to the cut $(V_1, V_2)$. Thus, the size of the cut must be at least $v_1$, which leads to a contradiction.
Again, if possible, let us assume that $U \cap V_2 = \emptyset$, which implies that $U \subseteq V_1$. Going by the definition of dominating set, each vertex $u \in V_2$ must be adjacent to at least one vertex belonging to $U$. Since $U \subseteq V_1$, this implies that each vertex $u \in V_2$ must be contributing at least one cross edge to the cut $(V_1, V_2)$. Thus, the size of the cut must be at least $v_2$, and hence at least $v_1$, which leads to a contradiction.
Since both our assumptions $U \cap V_1 = \emptyset$ and $U \cap V_2 = \emptyset$ lead to contradictions, any dominating set in the graph $G$ must have a non-null intersection with both both $V_1$ and $V_2$. Hence proved.
