Have been thinking for a while on how to prove the following statement, does anybody have an explanation for how to solve this type?
We have a undirected graph with 2n + 1 nodes, with the property that, for any subset of n of them, there is some other node that has an edge to all n. Prove that there is a node that has an edge to every other node, that is, prove there is a node of degree 2n.
This is an interesting problem, here are my current thoughts. If we consider attempting to disprove this question, we want to see if we can maintain this property while not having any vertex of degree 2n. Thus if we look at the compliment graph there must be at least n + 1 edges in it, with the additional restriction that every node has to have at least degree 1 (otherwise the node would be of degree 2n in the actual graph). Now the question for this compliment graph is what is its dominating number, and my thesis is that it is less than or equal to n in all cases, mostly from looking at small examples, but this is a bit tricky for me to prove.
However if we can show that the dominating number is at most n, then by selecting the n nodes that form this dominating set in the compliment, we see that this invalidates our property, as then for those n nodes in the dominating set, there is no node that is incident to all of them (as any other node is connected by an edge in the compliment, which means in the actual graph it is not connected, and thus can not be selected). Going to spend a bit more time thinking about this, let me know if it is simple to prove that the dominating number of the compliment is less than or equal to n.
Hope this helps a bit!
Hey thanks for the input! edit: Simplified Reasoning
I think you are really on to something, I think one can prove that the minimum dominating set is of most size n with the following fact from Wikipedia:
This is seen in https://en.wikipedia.org/wiki/Dominating_set: “If there are no isolated vertices in G, then there are two disjoint dominating sets in G; see domatic partition for details. Therefore in any graph without isolated vertices it holds that γ(G) ≤ n/2.”
Our compliment graph does indeed have no isolated vertices, as if it did those would have degree 0, and thus degree 2n in the actual graph, which is not allowed. Therefore this statement confirms that our compliment graph does indeed have a dominating set of size n or less.
Thanks for your input, hope our reasoning is sufficiently sound!
Hopefully this works:
Let S be the largest clique in the graph. Note that |S| ≥ n + 1 because otherwise there would be a vertex adjacent to all vertices of S and we could append it to S to get a bigger clique. Now let T be the set of vertices not in S. Since |T| ≤ n, we can find a node not in T (i.e. in S) which is adjacent to all elements in T. This is our required node.