7
$\begingroup$

If in a graph, any two vertices have an odd number of common neighbors, is it true that, there exists a vertex which is a 'universal friend', i.e adjacent to every other vertex?

(It is known that in that case the number of vertices has to be odd:

Prove that any graph G with an even number of vertices has two vertices with an even number of common neighbour )

If each of the odd numbers in question were 1, then this is the statement of the Friendship theorem.

$\endgroup$
2
  • $\begingroup$ There are certainly graphs with an even number of vertices that do not have a vertex that's adjacent to everything else. The smallest connected example is a path graph with 4 vertices. Do you intend for the wording "in this case" to imply additional conditions on top of having an even number of vertices? $\endgroup$ Mar 29, 2018 at 12:56
  • $\begingroup$ Sorry the way I wrote it was confusing. I meant to ask if there's a universal friend in the graphs where each pair of vertices has an odd number of common friends; and which necessarily have an odd total number of vertices. $\endgroup$ Mar 29, 2018 at 13:05

1 Answer 1

2
$\begingroup$

As a counterexample, consider the Kneser graph $K(6,2)$: its vertex set consists of all $15$ subsets of $\{1,2,3,4,5,6\}$ of size $2$, and two vertices are connected whenever they correspond to disjoint subsets.

Kneser(6,2)

Then any two non-adjacent vertices have $3$ common neighbors: for example, $\{1,2\}$ and $\{1,3\}$ have common neighbors $\{4,5\}$, $\{4,6\}$, and $\{5,6\}$. Any two adjacent vertices have $1$ common neighbor: for example, $\{1,2\}$ and $\{3,4\}$ have common neighbor $\{5,6\}$.

However, there's no vertex adjacent to all other vertices; in fact, $K(6,2)$ is regular of degree $6$.

(Kneser graphs are often good counterexamples for things; the Petersen graph, which is $K(5,2)$, is the most popular of these. However, in this instance, I admit that I just searched all of the graphs in Mathematica's database until I found one with this property.)

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .