19

Let $G$ be a simple graph on $n$ vertices $(n > 3)$ with no vertex of degree $n − 1$. Suppose that for any two vertices of $G$, there is a unique vertex adjacent to both of them. It is an exercise from A Course in Combinatorics, van Lint and Wilson, to prove that such a graph is regular.

My question, however, is whether graphs satisfying the given constraints even exist. While discussing the original exercise during a problem-solving session, someone asked if we could come up with an example of a graph where every pair of vertices have an unique common neighbor, and there are no global vertices. Neither were we able to come up with a concrete example or procedure for construction, nor did we establish a proof that no graph has these properties.

Any suggestions?

Note: as for proving that such a graph is regular, it turns out to be fairly straightforward, the rough idea is to pair off the neighbors of every pair of vertices using the unique-common-neighbor criteria to establish the fact that every pair of vertices have the same degree, and then a transitivity argument, with the help of the no-global-vertex constraint, gives us that the graph is regular.

Neeldhara
  • 599
  • 2
  • 15

1 Answers1

17

If you get rid of the "no vertex of degree $n-1$" condition, the graphs with the property that every two vertices have exactly one common neighbor are exactly the friendship graphs (a set of triangles glued together at a common vertex); as the linked article describes, this is a theorem of Erdős, Rényi, and Sós. But obviously, all such graphs have a vertex of degree $n-1$; the only regular one is a triangle. So the answer to your question is that, no, a graph with the common neighbor property and without a degree-$n-1$ vertex does not exist.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • Why thank you - this is excellent. It also explains all the difficulty that we were having with constructing these graphs without the global vertex! – Neeldhara Aug 29 '10 at 21:47