Combinatorics · Graph theory · Regular graphs · Triangle free graphs · Extremal construction
A mole has dug a number of underground rooms and joined them by tunnels, in such a way that from every room exactly \(3\) tunnels lead out, to \(3\) different rooms. Tunnels meet one another only at rooms. Moreover, among any \(3\) rooms there are always \(2\) that are not joined by a tunnel.
Prove that the mole has dug at least \(6\) rooms. Is it possible that the mole has dug exactly \(6\) rooms?
Sign in to check answers, open hints, read the full solution, and track your progress. Statements are always free.
Slovenian High School Mathematics Competition for Vega Awards (MaSSA), drzavno (national) round 2003, 1. letnik, category A, problem 4. Organized by DMFA Slovenije (Society of Mathematicians, Physicists and Astronomers of Slovenia). Source