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.
Best Answer
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).