Le Monde puzzle [46]

This week puzzle in Le Monde does not make much sense, unless I miss the point: in an undirected graph with 2011 nodes, each node is linked with at least 1005 other nodes. Is there always a node that is linked with all the nodes? If I take the first two nodes, 1 and 2, if there were no common node, the 1005 nodes linked with 1 would differ from the 1005 nodes linked with 2 and would not include 2. This corresponds to 1+1005+1005+1=2012 nodes… Sounds too easy, doesn’t it?!

Update (111810): Easy, too easy! Robin pointed out to me yesterday that this proves that 1 and 2 share a neighbour, nothing more. His counterexample to the existence of a common neighbour is to create nodes from node i to any node but (i-1) mod n and (i+1) mod n, which makes a graph with n-3 edges leaving from each node and still no common neighhbour! Conclusion: I should not try to quick-solve puzzles at 4:38am…