<p>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 <a href="http://en.wikipedia.org/wiki/Friendship_graph">friendship graphs</a> (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.</p>

CC BY-SA 2.5
2010-08-29T21:47:44.330Z
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
CC BY-SA 2.5
2010-08-29T18:18:49.073Z
2010-08-29T18:18:49.073Z
David Eppstein
<p>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 <em>A Course in Combinatorics</em>, van Lint and Wilson, to prove that such a graph is regular. </p>

<p>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. </p>

<p>Any suggestions?</p>

<p>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.</p>

<graph-theory><co.combinatorics><puzzles>
Construction of graphs where every pair of vertices have an unique common neighbor
Neeldhara
# Construction of graphs where every pair of vertices have an unique common neighbor

(Asked by: username_0 on 2010-08-29)

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.

**Tags:** graph-theory, co.combinatorics, puzzles

---

## 1 answers

### Answer by username_1 on 2010-08-29. Score: 17 | Accepted answer

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](http://en.wikipedia.org/wiki/Friendship_graph) (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.

> **Comments:**
> **username_0**: Why thank you - this is excellent. It also explains all the difficulty that we were having with constructing these graphs without the global vertex!  

---

