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.
