19
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why thank you - this is excellent. It also explains all the difficulty that we were having with constructing these graphs without the global vertex! $\endgroup$ – Neeldhara Aug 29 '10 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.