The following is a theorem in graph theory that has a nice 'real world' interpretation:
Suppose $G$ is a finite simple graph in which any two vertices have precisely one common neighbour. Then there is a vertex adjacent to all other vertices.
The word "precisely" is necessary here; if we replace it by "at least" then the statement is false.
My question is: What is the smallest counterexample to this false statement? I've found this one:
I've convinced myself that this is indeed the smallest counterexample, but my "proof" is very cumbersome and ugly. It is barely anything more than checking all smaller graphs. Then again I know practically no graph theory. Is there an elegant way to prove this is the smallest counterexample, if it is that?
Suppose $G$ is a graph in which any two vertices have at least one common neighbour, but no vertex is adjacent to all other vertices. Let $a$ be a vertex, $b$ a vertex not adjacent to $a$, and $c$ a vertex adjacent to both $a$ and $b$. By assumption, there is a vertex $d$ not adjacent to $c$ (and this can't be $a$ or $b$). A common neighbour to $a$ and $d$ can't be $b$ or $c$, so it is a new vertex $e$. That's $5$ vertices already. If we had a smaller counterexample than yours (in terms of number of vertices), it would need $5$ vertices, so we can't afford any new vertices. Now $b$ and $d$ need a common neighbour, which can only be $e$. Since $e$ can't be adjacent to everything, it can't be adjacent to $c$. But then $a$ and $c$ have no common neighbour.