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.
Problem
Source: Mexico National Olympiad Mock Exam 2019 P5
Tags: combinatorics, graph theory, friendly
Pluto1708
16.10.2019 18:07
This is just the definition of Dominating sets!
Hamel
16.10.2019 21:30
Omg 0 originality. You could use Halls theorem to prove it.
MathGenius_
16.10.2019 21:40
use marraige theorem
plagueis
16.10.2019 21:48
Can you share a solution with Hall's Marriage Theorem? Which would be the components? The solution I know (without using it) involves dividing into spanning trees and coloring with one of two colors.
Hamel
16.10.2019 22:04
Aight. Consider the smallest possible such set A and let B be the set of other vertices. And take a random set of vertices of A. The neighbourhood of that set in B cannot be less than the size of this subset since then we could replace the subset in A with their neighbourhood. Hence, Halls can be applied. Ie there is a perfect matching from A to B and A<=B and thus A<=n/2.
Math5000
22.10.2019 04:57
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).
RayThroughSpace
22.10.2019 05:39
Yikes... well on the bright side, I get to review graph theory Partition the graph $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. Proof: Take the partition with the maximum crossing edges. If a vertex has more neighbours in its own subgraph, move it to the other side and the number of crosses increase, a contradiction. Now a partition $V_1 \cup V_2$ clearly satisfies the conditions of the problem.