5
$\begingroup$

There are $n\geq 2$ people at a party. Each person has at least one friend inside the party. Show that it is possible to choose a group of no more than $\frac{n}{2}$ people at the party, such that any other person outside the group has a friend inside it.

This is just the definition of Dominating sets! I think I could use the marriage theorem or Hall's theorem... the solution I know (without using it) involves dividing into spanning trees and coloring with one of two colors.

$\endgroup$
4
$\begingroup$

We can assume without loss of generality that the graph generated by the connections is connected (you can deal with connected components separately).

Consider a minimal spanning tree of the graph, and pick an arbitrary node in the tree. Color it red. Color all of its neighbors green, then color all of the green nodes' neighbors red, etc, until the whole graph is colored. Note that since we are working with a tree, this is possible to do consistently. Then, consider the color which has fewer nodes. Take all of the nodes from that color and place them in your set. It is obvious that the resultant set is in fact a dominating set, and that the number of nodes chosen is at most $\frac n2$ since we have at least $2$ nodes (thanks to everyone having a friend).

$\endgroup$
3
$\begingroup$

You can partition the graph as $V = V_1 \cup V_2$, where each vertex in $V_1$ has at least as many neighbours in $V_2$ as in $V_1$ and vice versa. To prove this, take the partition with the maximum amount of crossing edges. If a vertex has more neighbours in its own subgraph, when you move it to the other side, the number of crosses will increase, a contradiction.

Now, we're done, since such a partition $V_1 \cup V_2$ clearly satisfies the conditions of the problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.