## Le Monde puzzle [46]

**T**his 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…

October 21, 2011 at 12:14 am

[...] puzzle in Le Monde this weekend is not that clear (for a change!), so I may be confused in the following [...]

November 25, 2010 at 12:49 am

[...] connection with Le Monde puzzle #46, I eventually managed to write an R program that generates graphs with a given number n of nodes [...]