Graph Theory: Friendship Theorem and Freshman's Dream

The 

Friendship

Theorem

Dr. John S. Caughman

Portland State University

(a+b)

p

=a

p

+b

p

…mod p

…when a, b are integers

…and p is prime.

“Freshman’s Dream”

Freshman’s Dream Generalizes!

(a

1

+a

2

+…+a

n

)

p

=a

1

p

 +a

2

p

 +…+a

n

p

…mod p

…when a, b are integers

…and p is prime.

(a

1

+a

2

+…+a

n

)

p 

= a

1

p

 +a

2

p

 +…+a

n

p

tr(A)

 p

 = tr(A

p

)    (mod p)

tr(A)

 p

 = tr(A

p

)   (mod p)

tr(A

 p

)

= tr((L+U)

p

) 

=

 tr(L

p

 +U

p

)

          = tr(L

p

)+tr(U

p

)=0+tr(U)

p

 = tr(A)

p

Note:

tr(UL)=tr(LU) so cross terms combine , and coefficients =0 mod p.

The Theorem

If every pair of people at a party has

precisely one common friend, then there

must be a person who is everybody's

friend.

Cheap Example

Nancy

John

Mark

Cheap Example of a Graph

What a Graph 

IS

:

Nancy

John

Mark

Nancy

John

Vertices!

Mark

What a Graph 

IS

:

Nancy

John

Edges!

Mark

What a Graph 

IS

:

Nancy

John

Mark

What a Graph 

IS NOT

:

Nancy

Loops!

Mark

John

What a Graph 

IS NOT

:

Nancy

Loops!

Mark

John

What a Graph 

IS NOT

:

Nancy

John

Directed edges!

Mark

What a Graph 

IS NOT

:

Nancy

John

Directed edges!

Mark

What a Graph 

IS NOT

:

Nancy

John

Multi-edges!

Mark

What a Graph 

IS NOT

:

Nancy

John

Multi-edges!

Mark

What a Graph 

IS NOT

:

‘Simple’ Graphs…

Nancy

John

•

 Finite

•

 Undirected

•

 No Loops

•

 No Multiple Edges

Mark

Let G be a simple graph with n vertices.

The Theorem, Restated

If every pair of vertices in G has precisely one

common neighbor, then G has a vertex with n-1

neighbors.

Generally attributed to Erd

ő

s (1966).

Easily proved using linear algebra.

Combinatorial proofs more elusive.

The Theorem, Restated

NOT

 A TYPICAL “THRESHOLD”

RESULT

If 

more than n

 pigeons are placed

into 

n or fewer

 holes, then

at least one

 hole

will contain 

more than one

 pigeon.

If a graph with 

n

 vertices has 

> n

2

/4

edges, then there must be a set of 

3

mutual neighbors.

If it has 

> n(n-2)/2

 edges, then there

must be a vertex with 

n-1

 neighbors.

Extremal Graph Theory

If this were an extremal problem, we

would expect graphs with MORE edges

than ours to also satisfy the same

conclusion…

1

1

2

1

2

3

1

2

3

4

4

4

4

2

Of the 15 pairs, 3 have 

four

 neighbors in common and 12 have

two

 in common. So ALL pairs have 

at least

 one in common.

But NO vertex has 

five 

neighbors

!

Related Fact – losing edges

Related Fact – losing edges

Related Fact – losing edges

Summary

If every pair of vertices in a graph has 

at least

one neighbor in common, it 

might

not

 be

possible to remove edges and produce a

subgraph in which every pair has 

exactly

 one

common neighbor.



The Friendship Theorem is listed among

Abad's “100 Greatest Theorems”



The proof is immortalized in Aigner and

Ziegler's 

Proofs from THE BOOK

.

Example

 1

Example

 2

Example

 3

STEP ONE:   If  x and y are not neighbors,

they have the same # of neighbors.

Why:

Let N

x

 = set of neighbors of  x

Let N

y

 = set of neighbors of  y

How to prove it:

How to prove it:

How to prove it:

For each u in N

x

 define:

f(u) = common neighbor of u and y.

How to prove it:

Pick 

u

1

 in N

x

.

x

y

u

1

How to prove it:

f(u

1

)

 = common neighbor of 

u

1

 and 

y

.

x

y

u

1

f(u

1

)

How to prove it:

How to prove it:

x

y

u

2

Pick 

u

2

 in N

x

.

How to prove it:

x

y

u

2

f(u

2

)

f(u

2

)

 = common neighbor of 

u

2

 and 

y

.

How to prove it:

How to prove it:

x

y

 u*

f(u)= f(u*)

 u

How to prove it:

x

y

 u*

f(u)= f(u*)

 u

How to prove it:

So f  is one-to-one from N

x

 to N

y

.

x

y

 u*

f(u)= f(u*)

 u

How to prove it:

So f  is one-to-one from N

x

 to N

y

.

x

y

 u*

f(u)= f(u*)

 u

So it can’t be true that  |N

x

| > |N

y

|.

How to prove it:

So f  is one-to-one from N

x

 to N

y

.

x

y

 u*

f(u)= f(u*)

 u

So            |N

x

| = |N

y

|.

How to prove it:

So it can’t be true that  |N

x

| > |N

y

|.

STEP 2:   Either some x has n-1 neighbors or

ALL vertices have same # of neighbors.

Why

:  Assume no vertex has n-1 neighbors.

Let  A = {x :  x  has max # of neighbors, k}.

        B = {y :  y  has <  k  neighbors}.

By Step 1, all in A are neighbors to all in B!

STEP 3:   If all vertices have k neighbors, then

n = k (k-1) + 1.

How to prove it:

Why:

STEP 3:   If all vertices have k neighbors, then

n = k (k-1) + 1.

Count paths of length 2…

How to prove it:

Why:

STEP 3:   If all vertices have k neighbors, then

n = k (k-1) + 1.

Count paths of length 2…

(  )

n

2

How to prove it:

Why:

STEP 3:   If all vertices have k neighbors, then

n = k (k-1) + 1.

Count paths of length 2…

(  )

1

n

2

How to prove it:

Why:

STEP 3:   If all vertices have k neighbors, then

n = k (k-1) + 1.

Count paths of length 2…

(  )

1

=

n

2

How to prove it:

Why:

STEP 3:   If all vertices have k neighbors, then

n = k (k-1) + 1.

Count paths of length 2…

(  )

1

=

n

n

2

How to prove it:

Why:

STEP 3:   If all vertices have k neighbors, then

n = k (k-1) + 1.

Count paths of length 2…

(  )

1

=

n 

(k)

n

2

How to prove it:

Why:

STEP 3:   If all vertices have k neighbors, then

n = k (k-1) + 1.

Count paths of length 2…

(  )

1

=

n (k) 

(k-1)

n

2

How to prove it:

Why:

STEP 3:   If all vertices have k neighbors, then

n = k (k-1) + 1.

Count paths of length 2…

n = k (k-1) + 1

?

Adjacency Matrix

Call vertices  v

1

, v

2

, …, v

n

.

Let A = n x n  matrix where:

     A

ij  

=  

1,      if   v

i

, v

j

  are neighbors,

     A

ij  

=  

0,      if not.

A  is called the 

adjacency matrix

 of  G.

Notice that the  trace of A  is  0.

{

A

2

 =

=

(A

2

)

ij

 = # common neighbors of v

i

, v

j

So……..   for our graphs…..

            A

2 

= (k-1) I  +  J.

(J = all 1’s matrix) 

(A

2

)

ij

  =  1           if   i, j  different, and

(A

2

)

ij

  =  k           if   i = j.

A

2 

= (k-1) I  +  J

(J = all 1’s matrix)

A J = (k) J

Now let  

p

  be a prime divisor of  

k-1

.

Then  

k = 1

   and   

n = k(k-1)+1 = 1

    (mod p)

So  A

2 

= J,  and  A J = J. 

(mod p)

Therefore,    

A

i 

= J    for all  i > 1

. 

(mod p)

A

i 

= J    for all  i > 1   

(mod p)

But         tr A

p

 = (tr A)

p      

(mod p)

So, modulo p,  we get:

     1 = n =  tr J =  tr A

p

 = (tr A)

p

 = 0.

Each pair

has 1 in

common

If x,y not

neighbors,

|N

x

|=|N

y

|

Some x has

n-1

neighbors

|N

x

|= k for

all x   and

n =k(k-1)+1

0=1

Either

Or

Moral

:

To make progress in almost

any field of math, find a way to

sneak linear algebra into it !

Related Result 1

Let m > 0 and k > 0 be integers. A graph with at

least m points is an (m,k)-graph if any m-tuple

of its points has exactly k common adjacent

points. The friendship theorem characterizes all

(2, 1)-graphs. For m > 2 and k > 0, there is only

one (m,k)-graph, namely the complete graph on

m+k points.

Related Result 2

There are other generalizations of finite

friendship graphs. Instead of graphs with edges

encoding pairs of friends and adjacency matrix

satisfying “A

2

-J is diagonal", one could

consider incidence matrices of finite

geometries: these are associated with bijections

between blockset and pointset of these

geometries.

Friendship references

 Huneke, Craig The friendship theorem. Amer. Math. Monthly 109 (2002), no. 2, 192--194.

 Brunat, Josep M. A proof of the friendship theorem by elementary methods. (Catalan) Butl. Soc.

Catalana Mat. No. 7 (1992), 75--80.

 Hammersley, J. M. The friendship theorem and the love problem. Surveys in combinatorics

(Southampton, 1983), 31--54, London Math. Soc. Lecture Note Ser., 82, Cambridge Univ. Press,

Cambridge, 1983.

Sudolsk\'y, Marián A generalization of the friendship theorem. Math. Slovaca 28 (1978), no. 1, 57-

-59.

 Skala, H. L. A variation of the friendship theorem. SIAM J. Appl. Math. 23 (1972), 214--220.

 Longyear, Judith Q.; Parsons, T. D. The friendship theorem. Nederl. Akad. Wetensch. Proc. Ser. A

75=Indag. Math. 34 (1972), 257--262.

 Wilf, Herbert S. The friendship theorem. 1971 Combinatorial Mathematics and its Applications

(Proc. Conf., Oxford, 1969) pp. 307--309 Academic Press, London

THANK YOU !