Studia Scieutiaruni Mathernaticarum Huugarica 1 (1966) 2 1 5-235 .

ON A PROBLEM OF GRAPH THEORY

by
P . ERDŐS , A . RÉNYII and V . T . SÓS 2

§ 0 . Introduction

Let G„ be a non-directed graph having n vertices, without parallel edges and

slings . Let the vertices of Gn be denoted by F 1 , . . ., Pn . Let v(P j) denote the valency
of the point P i and put
(0 . 1) V(G,) = max v(Pj) .
1ninn

Let E(G.) denote the number of edges of Gn . Let H d (n, k) denote the set of all
graphs Gn for which V (G n) = k and the diameter D (Gn) of which is --d,
(k=1, 2, . . ., n-1 ; d=2, 3, . . ., n-1) .
In the present paper we shall investigate the quantity
(0 .2) F, (n, k) = min E(Gn) .
G„ E Ha(n, k)

Thus we want to determine the minimal number N such that there exists a graph
having n vertices, N edges and diameter --d and the maximum of the valencies
of the vertices of the graph is equal to k .
To help the understanding of the problem let us consider
the following interpretation . Let be given in a country n airports ;
suppose we want to plan a network of direct flights between these
airports so that the maximal number of airports to which a
given airport can be connected by a direct flight should be equal
to k (i .e . the maximum of the capacities of the airports is pres-
cribed), further it should be possible to fly from every airport
to any other by changing the plane at most d-1 times ; what is OAbkbbk
the minimal number of flights by which such a plan can be
realized? For instance, if n = 7, k = 3, d= 2 we have F2 (7, 3) = 9 Fig. I
and the extremal graph is shown by Fig. 1 .
The problem of determining Fd (n, k) has been proposed and discussed recently
by two of the authors (see [1]) . In § 1 we give a short summary of the results of the
paper [1], while in § 2 and 3 we give some new results which go beyond those of
[1] . Incidentally we solve a long-standing problem about the maximal number
of edges of a graph not containing a cycle of length 4 .
In § 4 we mention some unsolved problems .
Let us mention that our problem can be formulated also in terms of 0 -1
matrices as follows : Let M=(a il) be a symmetrical n by n zero-one matrix such
T
Mathematical Institute of the Hungarian Academy of Sciences .
2
Eötvös L . University, Budapest.

Studia Scientiarum Mathennaticarum Hungarica 1 (1966)

216 P. ERDŐS, A . RÉNYI AND V . T . SÓS

thats ii =l, max .=k+1 and all elements of Md are ~- 1 . We want to

El]
1~i=n j=1
determine

Md (n, k) = min
Clearly
(0 .3) Md (n, k) = 2 Fd (n, k) + n .

This formulation shows the connection of our problem with non-linear programming .
We give for the case d=2 a third formulation of our problem which displays
its connection with the theory of block designs .
Let be given a sequence A,, A 2 , . . ., A n of subsets of the elements 1, 2, . . ., n
such that if j E A L then i E A j . Let us suppose that denoting by JAI the cardinal number
of the set A, we have max A j I= k . Let us suppose that for any i (I -_ i -_ n) and
1-~j~n
any j i such that j J A L there is a set A,, which contains both i and j (this is equivalent
by our supposition of symmetry to the statement that the sets A i and Aj are not
disjoint) . The problem is to determine

(0 .4) min ~Ai~ = 2F2 (n, k) .

=1

§ 1 . Some Basic Inequalities, and some Asymptotic Results

It is easy to see that if there exists a graph G n with V(G.)=k and diameter
d, then
(k-1) d -1
(1 . 1) n - I+k
k-2
(1 . 1) can be proved as follows : if V(GJ=k the number of points which can be
reached from a given point, say, P 1 by an edge is --k ; the number of points which
can be reached from P l by a path of length 2 is k(k-1) and finally the number
of points which can be reached by a path of length d is -k(k-1)d-1 . Thus if the
graph has diameter --d we have

(n-1)-k(1+(k-1)+(k-1)2+ . . .+(k-1)d-1) .
This proves (1 . 1) . If both n and k are odd, then Gn must contain at least one
point of valency --k-1 (because the number of points of odd valency cannot be
odd) ; thus in this case we get
(k _k l) d2_
(1 .2) n--1+(k-1) I .

Note that for the graph shown by Fig . 1, equality stands in (1 . 2) . For the graph
shown on Fig . 2 (the so-called Petersen-graph) equality stands in (1 . 1) with n =10,
k=3, d=2 .

Studia Scientiarunt Mathematicarum [Link] 1 (1966)

 ON A PROBLEM OF GRAPH THEORY 217

As regards F,,(n, k) we obtain easily the lower

bound
n(n-1)(k-2)
(1 .3) Fd (n, k) --
2((k- 1)`i - 1)
(1 . 3) can be proved as follows : every edge is itself a
path of length 1 ; it can be contained in at most
2(k-1) paths of length 2, but in this way each
path of length 2 is counted twice, thus the num-
ber of paths of length 2 cannot exceed E(G„) (k - 1) .
In general each edge can be contained in at most
3(k- 1) 2 paths of length 3, but in this way each
path of length 3 is counted three times, thus the
Fig . 2
number of paths of length 3 cannot exceed
E(G„) (k-1) 2 , etc . As in case G„ has diameter
d the number of paths of length d has to be at least ( 2 , we obtain

(1 .4) E(G„)(1+(k-1)+ . . . +(k- 1)d-1)

lJ
which implies (1 . 3) . Note that one has equality in (1 . 4) for the Petersen graph shown
on Fig . 2 ., further for n=5, k=2, d=2 because a cycle of length 5 has 5 vertices,
each of which has valency 2, it has diameter 2 and the number of its edges is 5 = 2. 2 .
It is clear from the above proof that one can have equality in (1 . 4) only for a
regular graph of order k, i . e . if E(Gn ) = 2 and if any two points are joined by
one and only one path of length -- d.
The first condition implies that if equality stands in (1 . 4) then there is equality
in (1 . 1) too . For the case d=2 this means that a necessary condition of equality
in (1 . 4) is n =k2 + 1 . It has been shown by A . J . HOFFMAN and R . R . SINGLETON [41
that a regular graph of order k, having k 2 + 1 points and diameter 2 exists only
for k = 2, 3, 7 and perhaps for k = 57 . Thus for d = 2 except for these values of
k one has strict inequality in (1 . 3) . However it has been shown in [1] that there
exists an infinite sequence of pairs (k,, n) such that k, -> -, n, and

F2 (n,:, k,) k; - 1
(1 . 5) lim
,-- n,(n,- 1) 2'

This is a consequence of the following

THEOREM 1 . If P is any prime power, there exists a graph G„ of order n = P 2 + P + 1
for which V(G„) = P + 1, which has diameter 2 and for which E(G„) _ 2 (0 12 + n) .
The graph G„ has also the property that it does not contain any cycle of length 4.
To make this paper self-contained we reproduce the proof of Theorem 1 given
in [1] .

Studies Scientiarzsm Mathematicarum Hungarica 1 (1966)

-2 1 8 P . ERDŐS, A . RÉNYl AND V . T, sÓS

PROOF OF THEOREM 1 . Let GF(P) be the Galois field with P elements . Let
us represent the points of the finite plane geometry .PG(P, 2) by triples (a, b, c)
where a, b, c are elements of GF(P), not all three equal to 0, and (~a, ),b, ~c) with
E GF(P), z 0 represents the same point as (a, b, c) . The number of different
points of PG(P, 2) is P 2 +P-{-1 . A straight line in PG(P, 2) is the set of all points
(x, y, z) which satisfy the equation ax + by + cz = 0 ; we denote this line by [a, b, c] .
The point (a, b, c) and the line [a, b, c] are clearly conjugate elements with respect
to the conic x 2 --y2 á-z 2 =0 . As well known there are P+ 1 points on each line,
any two different lines have exactly one point in common and through any two
given points there is exactly one straight line . Now we define the mapping T which
maps the point A = (a, b, c) into the line a = [a, b, c] and conversely. We write
TA =a, Ta=A . This mapping has evidently the properties : if the point B lies on
the line a = TA then the point A lies on the line (3 = TB ; if C is the point of inter-
section of the lines TA and TB then TC is identical with the line passing through
the points A and B ; A = (a, b, c) is on TA if and only if a 2 + b 2 + c 2 = 0, i .e . if A
lies on the conic x 2 +y 2 +z 2 =0 . Now let us define a graph G„ (n=P 2 +P+1)
as follows : the vertices of Gn are the points of PG(P, 2) ; the vertices A= (a, b, c)
and A'= (a', b', c') are joined in G n by an edge if and only if A' is lying on TA (and
thus A is lying on TA') . Clearly a vertex A in Gn has the valency P or P+ 1 according
to whether A is on the conic x 2 +y 2 +z2 = 0 or not . V Thus

2 (n' 12 -n) P(P2+P+1) -- F(GJ

z
and
, 2 (n 3,1 2 +n) .
E(GJ-
1 (P+1)(P2+P+1)

Finally the diameter of G,, is equal to 2 . As a matter of fact any two points
A and B can be joined by the path ACB where C is the point of intersection of the
lines TA and TB . Besides this A and B can be joined by a single edge if A lies on TB .
But the point C such that the edges AC and BC both belong to Gn is in any case
unique ; thus Gn does not contain any cycle of length 4 .
Thus our Theorem is proved .
We deduce from Theorem 1 the following corollaries .

COROLLARY 1 . Put nk = k 2 - k + 1 ; then

F2 (nk , k) k - 1
(1 .7) fim inf
k-- nk(nk - 1) 2

" If P is prime, there are P+1 points on the conic and thus

E(G„)
+ )z 1
= 2
~ 2 11112 if n~nn .

Studio Scientiarum Mathe?naticarum Hungarica 1 (1966)

 ON A PROBLEM OF GRAPH THEORY 219

PROOF OF COROLLARY 1 . By (1 . 3)

(i . 8) F2 (n, k) k , 1
n(n-1) - 2
further if k = P + 1, n k = P 2 + P + 1, by Theorem 1
(1 .9) F2 (P 2 -I p+1, P+1)~ 1 (P+1)(P2+P+1) ;
thus in this case
F2 (nk , k) k
(1 . 10) nk (nk -1) 21 I+- 1 ,
this proves our assertion .
Theorem 1 enables us also to solve - at least asymptotically - a problem
which was raised by one of us 27 years ago (see [2]) .Y
Let C„ denote the class of graphs having n vertices and containing no cycle
of order 4. Put
(1 . 11) µ(n) = max E(G„) .
G„ E C„

The problem is to determine the value of µ(n) . From Theorem 1 we deduce the
following
COROLLARY 2 . We have
lim µn312
1
(1 . 12) n = 2
n--
PROOF OF COROLLARY 2 . It follows clearly from Theorem 1 that if P is a
prime power, then putting n = P 2 + P + 1

(n3/2 - n) .
(1 .13) µ (n) - 2

It is possible that for these n the graph of Theorem 1 is extremal but we can-
not prove this . Clearly µ(n) is an increasing function of n, and thus it follows that
for any n we have
(1 .14) u(n)
Z [P2+P+1)312-(P2+P-{-1)]
where P is the largest prime power such that p2 + P + 1-_ n . Now evidently for
n--n 1 one can choose a prime p so that

n
(1 .15) vn - log p } n -1
n

After having written this paper we have been informed by W . G . BROWN that independ-
ently of us he has proved (1 .12), in the same way as we did . His paper will be published in the Bul-
letin of the Canadian Mathematical Society .

Studiz Scientiarum Mathematicarum Hungarica 1 (1966)

220 P . ERDŐS, A . RÉNYI AND V. T . SÓS

which implies for n~n i

2
n 1-lo g n) p 2 +p + 1 ~- n .

Thus we have for any n -n i

(1 .16) n3/2
µ(n) - 2
( 1- l0g3 n )
and thus
µ(n) 1
(1 .17) liminf
n-- n3 2 2

On the other hand it is easy to see (this follows also from the results of 1 . REIMAN
in [3]) that

(1 . 18) lim sup µ(n) 1

J?-- n 3 1 2 2

As a matter of fact, let Gn be a graph containing no cycle of order 4 . Let P 1 , P2 , . . ., P„

be the vertices of Gn and let us denote their valencies by v l , u 2 , . . ., vn . Now clearly one
can select from the set Ei of vertices joined by an edge to P i (2` pairs, and no
pair (Pj , Ph) can be contained in both Ei and E, with l i because otherwise P ; Pj PI P,,
would be a cycle contained in G,, . Thus we must have

(1 .14)
í n) .
Z „ (v1 2
Now we have
n

(1 .20)
and thus

(1 .21) 2n (J 2n / 2 ) n3 .
n
As clearly fv j = 2E(G„ ), we have

(1 .22) 4E 2 (G n ) - 2nE(G „) = n 3
which implies
n 3/2 1 n
(1 .23) E(Gn) - 1
2 4n + 4'
Thus
li(n) 1 1 1
(1 .24)
n312 - 2 4n + 4 .~n .

which implies (1 . 18) . Thus Corollary 2 is proved .

Stuc1m Seient?arum Mathematicarum Hungarica 1 (1966)

 ON A PROBLEM OF GRAPH THEORY 221

Let us note that weaker results have been obtained previously by E . KLEIN
µ(n)
(see [2]) and 1 . REIMANN [3], who proved lim inf 1 REIMANN's extremal
n-- n 2 j 2,
graph does not contain triangles either ; it is possible that among such graphs it is
optimal .
Note that for the pairs (n j , kj) for which according to Corollary I one has

(1 .25) lim
k
F2 (np j)k; - I
;_,_ nj (n j -1) 2
one has kj -Vn j . It was shown in [1] that there exists another sequence of pairs
(k,, n j ) such that
, k'-)kj
(1 .26) Jim Fz(n' = 1
j _,_ nj (nj -1)
a
but for this sequence of pairs one has lim ~~' _ + ~ .
nj
It remains an open question what is the value of the function g(c) defined by
F2 (n, k) k
(1 .27) g(c) = liminf
k2,n, n(n- 1)
n-~

for I < c +- ; we know only that g(c) is nondecreasing, z - ~ g(c) and lim g(c) ; 1 .

§ 2. Some Exact Results for d=2 .

In this § we deal with the exact value of F, (n, k) for k n - 1 . Evidently,

2
Fz, (n, n -1) =n -1, because the graph Gn in which one vertex is joined by an edge
with all others, has diameter 2, further V (G .) = n - I and E(G,,) = n -1 . It has
been shown in [1] that Fz (n, n - 2) = 2n - 4 (a graph G„ with V (G .) = n - 2 and
E(G„)=2n-4 and having the diameter 2 is shown by Fig. 3 ; another graph with
the same properties is shown by Fig . 4), further that FZ (n, n - 3) = FZ (n, n - 4) _
= 2n - 5 . (The corresponding extremal graphs are shown by Figs . 5 and 6 .)

Fig. 4

Studia Sci~iarum A]athen .aticarum Hungarica 1 (1966)

222 P . ERDŐS, A . RÉNYI AND V . T . SÓS

We shall prove now

THEOREM 2 . We have for n --13
2n-2
(2 .1) F2 (n, k) = 2n-4 for 3 k n-5 .

Fig . 5

PROOF OF THEOREM 2 . The extremal graph G„ with

n 3 21
V(G„)=k=n-1, 15<1-

and E(G„) = 2n - 4 and having diameter 2 is exhibited by Fig . 7 .

V(G„)=n-1, E(G,)=2n-4, 5,1~ n3 n - 13 .

Fig . 6 Fig. 7

Studia [Link] Maáhematicarum Hungarica 1 (1966)

 ON A PROBLEM OF GRAPH THEORY 223

Note that all vertices of G„ except P,, P2 and P 3 have the valency 2, further
v(P,)=n-1, v(P2)=n-1, v(P3 )=21-2 and by supposition 21-2-n-1 . Thus
V(Gn )=n-1 . Clearly G„ has diameter 2 and the number of edges of Gn is
= 2(n-/)+21 -2+2(n-3)
E(G„) = 2n-4 .
2
n + 21
We prove that for any G n with n ~ 13, V(G„) =n - l 5 3 and diameter
--
2 one has E(Gn) 2n - 4 .
n

As E(Gn ) = 75,v(Pi) we may suppose that G„ contains at least one point

2j=1
of degree 3 . If G n would contain no point of degree --2, then let us choose a point
of degree 3 ; let this point be P, . Let the points connected by an edge with P, be
denoted by P2 , P 3 and P4 . As every point can be reached from P, by a path of
length --2, we must have v (P2 ) +v (P3 ) + v (P4) -n -1 .
Now if there would be a point among the points P s , . . ., Pn which would be
connected with more than one of the points P 2 , P3 , P4 we would have v(P 2 )+
+v(P3)+v(P4) Win ; as all other points have degree ~3 it would follow
n
v(P i ) n+3(n-3) = 4n-9
=1
and thus E(G n)>2n-5 i .e . E(G n )~2n-4, which was to be proved . Thus we may
suppose that all points P i (5 -- i -- n) are connected with one and only one of P2i P 3
and P4 ; similarly we can suppose that P2i P 3 and P 4 are not connected with each
other because this would again imply v(P 2 ) + v(P 3 ) + v(P4) --n and thus E(Gn)1-
2n - 4 . If there is at least one among the P, with 5 -- i - n which has degree > 3,
it again follows that E(G„)--2n-4 . If however all have degree 3, let us suppose
that V (P2) =min (v (P2), V(PA v(P 4 )) which implies V (P2) n3I . Let P s be
connected with P 2 . Then v(N S 3 and let the three points connected with P, be
P 2 ,P ;, and P, ; clearly i>5 and j>i>5 . But then v(P2)+v(Pj)+v(Pj)--n-1
and thus
2(n-1)
6 = v (P) + v (P,)
3
that is n 10 .
As we supposed n 13, this case is settled .
The case when there is a point P, of valency 1 is easily settled, because if this
point is P,, and P, is connected with P2 only, then P2 has to be connected with
the remaining n-2 points too, and thus would have valency n-1 . Thus the only
case which remains to be settled is when min v (P i) = 2 . Suppose v (P,) = 2 and
1-inn
let P, be connected with P 2 and P 3 . Then all remaining points have to be connected
either with P 2 or with P3 or with both .
Let C, denote the class of points P i with i 4 connected only with P 2 , and
c, the number of elements of C, ; let C 2 be the class of points P i with i --4 connected
only with P 3 and c 2 the number of elements of C 2 ; finally let C 3 be the class of points
connected with both P2 and P 3 , and c 3 the number of elements of C 3 . Clearly

Studies Scientiarum Mathematicarum Hunyarica 1 (1966

2.24 P . ERDŐS, A . RÉNYI AND V. T . sÓs

c, + c2 + c 3 = n - 3 . As the valency of P 3 cannot exceed n - I and P 3 is connected

with every point in G„ except itself and the points in C,, we have c l --I-2 3 .
Similarly c 2 ~-- 1-2-3 .
The number of edges in G„ the existence of which is already established is
clearly c l + c2 -P 2c 3 + 2 = n + c 3 -1 . Let us call these the edges of the first kind,
and the remaining edges those of the second kind . As the graph has diameter 2,
every point of C, has to be connected by a path of length - 2 with every point of C 2 .
Such a path can not contain an edge of the first kind . Thus the graph G' consisting
of the edges of the second kind has to be connected . Now three cases are possible.
Either G' contains besides the points of C, and C 2 at least one further point from
the class C3 ; in this case it contains at least c, + c 2 + 1 points and thus there are
at least c 1 +c2 edges of the second kind, and thus the total number of edges is
E(G„) --n + c 3 -1 + c l + c2 = 2n - 4 . Or P2 and P 3 are connected by an edge ;
in this case we get again E(G„)-_2n-4 . Or P 2 and P 3 are not connected and G'
consists only of the points of C, and C 2 . In this case the connected graph G' is
either a tree or not . If it is not a tree, it contains at least cl + c 2 edges and thus we
obtain again E(G„) --2n -4 . If G' is a tree, it must have at least two end-points . We
may suppose that C, contains an endpoint of G' . Let x be the total number of end-
points of G' in C 1 . Then the sum of valencies (in G') of the points of C, is at least
x + 2 (c, - x) . As G„ has diameter 2 and P 2 and P 3 are not directly connected, any
endpoint of G' in C, has to be connected by a path of length 2 to P 3 , it follows that
for every endpoint P of G' in C, the single edge starting from P ends in C 2 . Let
y denote the number of points in C 2 which are connected with an endpoint of G'
in C, . If Q is such a point, clearly Q has to be connected with every other point
of C 2 , because otherwise there would not exist a path of length 2 from P to
these points . Now clearly no point of C 2 can be an endpoint of G', because it must
be connected to at least one point in C, and also to Q . Thus the sum of valencies
in G' of the points of C 2 ist at least 2(c2-Y)+Y(c2-1)+x. It follows that the
number of edges of the second kind is at least

2 e22 31
(x+2(c,-x)+2(c2-Y)+Y(c2-1)+x) . = cl+c2+Y( ' c l +c 2 ,
because, as we have shown, c 2 --3
Thus we have shown that E(G„) 2n -4 and the proof of Theorem 2 is complete .
Note that the restriction n =13 in Theorem 2 is necessary, because for n < 13
2-2
2n
there is no value of k between 3 and n - 5 .
2n 2
As regards the value of F2 (n, k) for k < 3 - - we can show that for n' 15

3n-3 k < 2n-2

-k-6 for
5 3
5n- 3 k 3n-3
(2 .2) F2 (n,k -4k-10 for 5

n +I1 _ k ` 5n9 3
4n - 2k-13 for

Studio Scientiarum Mathematicarum Hunyarica 1 (1966)

 ON A PROBLEM OF GRAPH THEORY 225

We give in what follows the extremal graphs for these 3 cases . That these are really
extremal can be proved in a way similar to the proof of Theorem 2, therefore we
leave the details to the reader .

The graph has four points of high degree ; let us denote them by A, B, C, D
and four groups of points .
There is a group denoted by AB, the points of which are joined to A and to B .
The group contains 2k-n points . In the group BCD (connected with B, C and D)
there are n -k -1 points . In the group AC (whose points are connected with A and C)
n-k-3
2
there are points ; finally in the group AD (the points of which are con-
--
nected with A and D) there are n - k - 3 - n k 3 2 points . Further the graph
contains the edges AB, AC, AD . The points A and B have the degree k. The whole
graph has 3n - k - 6 edges .
5n9 3 k < 3n5 3
THEXRMALGPFO

There are 5 points of high order, A, B, C, D, E.

The group AB has 2k-n points,
n-Ic-1
The group BCD has 2 points .
_[n-k-
2 1
The group BCE has n - k -1 points .
The group AC has 2k-n points .
The group ADE has 2n - 3k - 4 points .
Further the edges AB, AC, AD, AE, DE belong to the graph . The points A, B
and C have the valency n-k ; the total number of edges is 5n-4k-10 .

n 21 k< 5n9 3
THEXRMALGPFO

There are 6 points of high order, A, B, C, D, E, F.

The group AB contains 2k-n points .
n-k - 12
The group BCE contains points .

The group BDF contains n -k - 1 - n-k-1 2 points .

n-k-5
The group ADC contains points .
2
n-k5
The group AEF contain ; n - k - 5 - 2 points .
The graph contains further the edges AB, AC, AD, AE, AF. The graph has 4n- 2k-13
edges .

15 Studia Sc entiarum Mathematicarum Hunga ca-1 (1966)

226 P . ERDŐS, A . RÉNYI AND V . T, SÓS

n +II
For k < we cannot determin ; Fz (n, k) c xactly . However, we can get
a fairly good upper bound by constructing graphs of diameter 2 by the following
( r) of the points of a graph G„ into r groups of
principles . We divide all but
2
approximately the same size . We connect the points of each pair of groups withh
one of the remaining points, and connect as many of these point3 with each other

z ze 2

ae P

Fig. 8

as needed . For instan ve if r = 4, n=41+6, we put l points in each of 4 groups, connect

each of the 6 pairs of groups with one of the remaining 6 points, and connect eachh
of these points with that point which is connected with the other two groups . The,
graph obtained is shown by Fig . 8 . It follows that

(2 .3) F2 (41+6, 21+1)--121+3 .

§ 3. Some Remits for d 3.

We prove first
THEOREM 3. We have for every n, every k -
. n -1 and d - 3

3
2
(3 .1) Fd (n, k) I 1-
kn
PROOF OF THEOREM 3 . Let us put

Clearly we may suppose 6 < 1, because otherwise (3 . 1) is trivially fulfilled . We have,

evidently
4
(3 . 3)
k d/ 3

Studia Seieritiarum Mathematicarum Hungarica 1 (1966)

 ON A PROBLEM Or GRAPH THEORY 227

We may suppose n > k d 1 , because any graph G„ with diameter - d is connected

and thus has at least n -1 edges ; thus F3 (n, k) n -1 and if n --Ic a- i the inequality
(3 . 1) is trivial . Thus we have to prove (3 . 1) only for k d-1 < n < .e . for (64n) Id < I
64 i
<k<n 1 Id - i
Let G„ be a graph having n vertices, diameter d and such that V(G„)=k.
kd4n
LetusdnobyX l , . . .,X S those vertices of G„ the valency of which is <
6
let Yi , . . ., Y„_ s be the remaining vertices of G,, . We have clearly
~~ - S
1
(3 .4) E(G „) =2 (X i)-I- ~ v(Yj )I >?kd _ l~ n •
1-1
Thus if

s=n 1- 2
we have
. nz
(3 .5) E(G „) kd _1

Thus we have to consider only the case

b(1 - b)
(3 .6) s ::- n 1 -
2

We distinguish two cases .EithervyX , (1 -- i -- s) is connected with at least

~1 -
2 ] ~_d r of the vertices Y,, or not . In the first case we have

z
(3 .7) E(G „) -- s 1- 2 1 - ( 1 -b) kd _, .
kd

ThuswemaypotherisanX , - sayX i - which is connected with less

than 1 -
wecanrh,stigfromX
I Z~ kd
1 Y,-s . We shall show that this case is impossible . By supposition
l , every vertex of G by a path of length -- d . Let us
considerfthpasrtingfomX l , the next vertex of which is an Y; .
As Yj can be chosen in < 1 - ~ , ways, and all vertices of G„ have valency
Z
.k, the number of such pathes is at most

(3 .8) i (1-+-(k-1)-+- (k-1)z + . . . +(k-1)d-i)Z~n .

I1-2)kd

* We may also suppose that k-64 .

15* Stuclia Scientiarum Mathe matic¢rum Hungavica 1 (1966)

228 P . ERDŐS, A . RÉNYI AND V . T . SÓS

LetusconwhepatsoflnghdtarifomX 1 , on which the point

nextoX I , is an X i . The number of such pathes is clearly at most

kd% (1+ k4n5

(3 .9) (1+(k - 1) + . . . +(k-1)d-2)) < 3

It follows from (3 . 8) and (3 . 9) that the total number of vertices which can be reached
fromX i by a path of length -d, can not exceed n 1- 66
which is --n-2 if n
12
,
and this is true if n - l k 64 ; thus we arrived to a contradiction and this proves
our theorem .
2
To show that the order of magnitude
of the lower estimate of F3 (n, k)
k2
is best possible, consider the following graph G„ : Take a complete graph G r having
r vertices, and connect each vertex of G r with r -1 new points . Thus we obtain
a graph G„ with r (r -1) -} r = r 2 = n vertices . Clearly one has k = V (G„) = 2r - 2,
z
D(G„)=3 and E(G„)=2 r(r-1) . Thus E(G„)-k .
2
In this example k=2(~n -1) ; by slightly modifying this example we obtain that

k2z
F3 (n, k) < (c + 1)2 +
1
if k - en where 0 < c < 1 .

To show that F3 (n, k) is of order of magnitude nfor k - ~ )l n where

0 < A- :: 1 we have to apply a more involved construction . Let us consider a graph
G„ which has the vertices Pgi ; where l g-- 1, 1--i s, l-j-s and the vertices
Q ghi where 1--g<h--l and 1-i--s ; thus n=1s2 +(2)s. Suppose that the edges
of G„ are as follows :
a) Pgi; and Phil are both connected with Qghi for 1--g < h --<I, i, j =1, 2, . . ., s .
b) Qg hi, is connected with Q g hiz for 1 - it -S, 1 i2 S, it 7z i2, 1 --g < h --1 ;
C) Q g , h , i and Qa2h2 i are connected for 1 g, < h l and 1 ~ g2 < h2- 1,
i=1,2, . . .,s .
Clearly

2,
-2 ~') s2+ (SI + ~
E(G") 2 (1)
22 2
further v(Pgij)=s-1 and
l
/ 2
v (Q ghi) = s fi l -1 2 1

[Link] Mathematicarum Mmyari .ca 1 (19ár,)

 ON A PROBLEM OF GRAPH THEORY 229

Z
and thus V(G,)=s+l+ -2 . Thus we obtain
2
Z
+~1)S,S+l+(1+])/(181)(1-2)
F,Ils 21<2[jS2+IjISI+ s.
2 - 2 2
By other words by choosing for Z an arbitrary fixed natural number and for s tending
to + -, we obtain an infinite sequence of pairs n, k such that
l'l a
k - and F3 (n, k) /(1-1) .
4 k2

Thus for arbitrary small a, :~- 0 there exists an infinity of pairs n, k such that k - ;L~n and
F3 (n, k) < 5 n
4a4 * k22 .
Let us study now the behaviour of F3 (n, k) for large values of k . Clearly
F3 (n, k) = n -1 if k - because the graph Gn shown on Fig . 9 has diameter 3
2
V(Gj = k and Gn is a tree, thus it has n -1 edges ; this result is best possible because
a connected graph Gn cannot have less than n-1 edges .

Fig . 9

We prove now the following

3
THEOREM 4 . If + l +s- 1 -- k s +s - 2 where s =1, 2, 3, . . 2 then
s
F3 (n, k)=n+(Z

PROOF OF THEOREM 4 . The e ase s= 1 has been settled above . Let us consider
first the case s=2 . Suppose Gn wou'd be a tree of diameter 3 and V(G .)=k - 2 ,
and let P i be an endpoint of G n (such a point exists as every tree has at least two

Studia Scientiarum Mathematicarum Hungarica 1 (1966)

230 P . ERDŐS, A . RÉNYI AND V. T . SÓS

endpoints) . Let P 2 denote the single point connected with P i by an edge, and let
P3, . . ., P, be all the other points connected with P z ; as V(G„)=k we have l--k+1 .
The remaining n -k-1 --k-1 --l-2 points have to be connected with one of the
points P 3 , . . ., P, because otherwise it would be impossible to reach them from
Pi by a path of length --3 . But they can not be all connected with the same point
P; (3 j -- l) because this point would have valency lc. Let P, and P, be two
points (Z < r < s n) such that P, is connected with Pi, a nd P, with P; (3 - i -j 1) .
Then the (unique) path from P, to P, has length 4 ; this contradiction shows that
F3 (n, k) n for k, 2 .

3+ I
On the other hand Fig . 10 shows a graph G„ with V(G„) =k where --k 2
which has diameter and contains exactly one cycle (a triangle) and thus E(G .) =77 .
3
3
This completes the proof of the fact that F3 (n, k) = n for + 1 k 2.
Note that for n=2k+1 there is another extremal graph G2k+1 of diameter 3,
for which V(G2h+1)=1c and E(G,k+,)=2k+1, shown by Fig . 11 .

VCG 2k+1 )=k, E032k + i)=2k+i, D (G2k+j )=3

Fig . 10 Fig . II

Now we pass to the case s 3.

3

Let G be a graph with V(G„)=k 1s+,+s-l-k_

and D(G„)=3 . LetX
s +s-2 ;s<
l , . . ., X, be the endpoints of G,, . As the remaining n-1 points
2

all have valency --2, and at least one among them has valency k, we have

E(G,) - 2 (1+k+2(n-1-1» = n- 1 + 2 -1 .

Studia Seientiárum Mathematicarum Hungarica 1 (1966)

 ON A PROBLEM OF GRAPH THEORY 231

Now if E(G„) --n + ( ) - 1, we have nothing to prove ; if however E(G.) n +

2
+(2)-1 we get
l :~-k-s(s- 1) -s-1
thus 1--2 . Let Y1 , . . ., Y„ denote those vertices of G„ which are connected with
at least one X, (1 --j l) .
Clearly Yi and Y, are connected by an edge (1--i <j--v) because otherwise
therwouldnxistaphofleng3ctiheX h -s . Thus it is sufficient
to consider the case v--s, because every connected graph G„ containing a complete
s+ 1-graph has at least n -1 + Z)
edges . Let us suppose therefore that v-- s.
We prove first that v mss . LethndpoiX,bec tdoY 1 . Let Z1 , . . . Z r
denote all the points connected with Y, which are not endpoints of G n . As every
pointfG„caberhdfomX,byapthfleng -- 3, if Y, is connected
r
with p endpoints then we have f v(Z,,)'n-p-1 thus
h=1
3n2 3 - r21
E(G„) I (n-p- l+p+t-+1+2(n-l-r-1))=
thus in case E(G,,) < n + ( ) -1 we get
Z
l--n-r-s(s-1) .
As however each Y, has valency k, it can be connected to at most k oftheX ,-s,
and Y, only to k-rX L s ; thus
(v-1)k+k-ran-r-s(s-1)

and therefore, in view of s 2 , we obtain v ::- s -1 i .e . v --s . Thus we have c my

to consider the case v=s . Now if v = s there exist in G„ at least s points which
are not connected to any of the Y,-s because these have valencies --k and thus
the total number of points connected with them is --s(k-(s-1)) :n-s . Let W
be such a point .
NowclearyWhstobcnedwithacX h by a path of length 3 and
therefore with each Y; by a path of length 2. Let U1 , . . ., Ut be the points connected
with W, then each Y, is connected with some U. Thus it follows

E(Gj (21+s(s-1)+2s+2t+2(n-I-s-t-1)) _
2

= I +s+t+n-I-s-t-1 =n+ (2)-1 .

11-2ll
Thus F3 (n, k) n + ( 2) . On the other hand consider the graph Gn of the follow-
ing structure : let us take a complete graph G 5+ , having s + 1 points, and connect

Studia Scientíarum Mathenaaticaruin Hungarica 1 (1966)

232 P . ERDŐS, A . RÉNYI AND V. T . SÓS

each of these points except one with k - s endpoints, and the last with n - s (k - s) -
-(s+l) points . (Clearly O--n-s(k-s)-(s +1)--k-s) .
Thus we obtain a graph G„ with V(G„) = k, D (Gj = 3 and E(G.) = n +
( s) -1-
This completes the proof of Theorem 4 .
Let us consider now F4 (n, k) . Clearly
F4 (n, k)=n-1
if k-fn-1 .
This can be seen as follows . Fig . 12 exhibits a tree of diameter 4 showing that
F4 (k2 + 1 , k) = k2
Clearly if (k -1) 2 + 1-- n < k2+1' we obtain a graph G„ exhibiting F4 (n, k) _
=n -1 by omitting from the graph on Fig . 12 k2 + 1 - n endpoints . We shall.
prove now
pk .2
Pk+3
THEOREM 5 .
4
1
F4 (k 2 +2,k)-k 2 +1+2 5 (k=2,3, . . .).
P2k P2kai
PROOF OF THEOREM 5 . Let Gkz+2 be an ext-
P2k+2
remal graph i .e . one which has k 2 + 2 points,
diameter 4, satisfies the condition V(Gk2 +2 )=k and
has F4 (k2 + 2, k) edges .
Pzk-l Let X I , . . ., X, n be the points of Gk z +2 having
valency --2, and let G,*n be the subgraph of Gk2+2
spanned by these points . We assert that each point
X'hastevlncy~2i G,*„ too . Suppose that
~° Pk2 k+a X I is an endpoint of GI*,,, andthX 2 is the only
Pk2-k+,,
pointfGmwhcX I is connected .ClearyX I
Pkz is connected with at least one endpoint Y I of
G k z +2 because it has valency 22 in C'-k2+2, thus it
Fig. 12 is connected with some point of Gk2+2 different
fromX Z and this point cannot be in G n*, and
thus is an endpoint of G k 2 +2 . Every point of Gk 2 +2 can be reached by supposition
from YI by a path of length 4 . However the number of points which can be
reached from YI by such a path is clearly
-2k-1+(k-1) 2 =k 2
which is a contradiction . Thus in G,*n each point has valency --2 . As the diameter
of G,*n is --4, it follows from (1 . 1) that G,*„ contains at least one point of valency
4 4
fm -1 ; thus the number of edges of G,*n exceeds (m -1) + i ( ~m -1) . Each point
in G,*„ can be connected with at most k-2 endpoints of Gk 2 +2 thus Ic e +2-m+
k2 + 2
+m(k-2)=m(k-1) and therefore m- k- 1 ,k+1 ; thus
4
1 "-
E(Gk2+z) k2+1+ 12 (Vm-1) --k2 +1+ 2 ~k .
Thus Theorem 5 is proved .

Studia. Seientiarum Mathematicarum Hungarica 1 (1966)

 ON A PROBLEM OF GRAPH THEORY 233

Note that the statement of Theorem 5 is trivial for k --16, because it states
only what we know already that if D(Gk2+2) =4 then G,2+2 can not be a tree .
To get an upper estimate for F4 (k2 +2, k) - k2 consider the following graph .
Take a graph Gk+s with V(Gk+s)=k, D(Gk+s)=2 and E(Gk+s)=2k+6 ; such
a graph exists according to Theorem 2 if k 8 (see Fig . 7 with l = 5) . This graph
has k + 2 points of valency 2 . Connect k out of these points with k - 2 new points
each and one with k - 3 new points . Thus we get a graph Gn with n = k 2 + 2 points,
such that V (G .) = k, D (Gn ) = 4 and E (G.) = k 2 + k + 3 . Thus
F4 (k2 +2, k)--k 2 +k+3 .

§ 4 . Some further Remarks and Unsolved Problems

First we formulate some general principles of construction which were implicitely

used above .
If Gn is a graph of diameter d, and such that V(G,,)=k, then if G,' is not regular,
we may construct from G„ a graph GN of order N= n + kn - E(G,,) with V (GN) = k
and diameter d+2, by connecting each vertex P i of G n which has valency v(P) <k
with k -v (P) new points . Thus
(4 . 1) Fa+2(n+kn-2Fa(n, k), k)-kn-F,i (n, k) .
For instance we have shown that F2 (n, n - 5) = 2n - 4 . It follows immediately
from (4 . 1) that
F4 (n 2 -8n+8, n-5)-n 2 -7n+4 .
Notice that for each value of d, the extremal graphs Gn with V (G,,) = k, D (G n) = d
and having a minimal number of edges, are trees if k is sufficiently large, k -- Ud (n) say .
We have implicitely shown that
(4 .2) UZ (n) = n -1
2
(4 .3) U3 (n)

(4 .4) U4 (n) _ / n -1 .
It can be shown that
1 + ~2n - 3
(4 .5) Us (n)
2
further that for any fixed s ~--- 3 and n->-
(4 .6) U, (n) - ~n
and

(4.7) U2s+ l. (n) - 2

The extremal tree of diameter 2s has a center, while the extremal tree of diameter
2s + 1 has a central edge .

Studio Scientiarum Maihematicaruvn Hungaríca 1 (1966)

234 P . ERDŐS, A. RÉNYI AND V. T . SÓS

Notice that if k decreases by one below the critical value U, (77), i .e . to Ud (n)-1,
there is a considerable increase in the value of F,,(n, k) if d is even, but not if d is
odd . As a matter of fact
FZ (n, U2 (n) -1) - Fz, (n, U2, (n)) _ (2n - 4) - (n -1) = n - 3
F3 (2k+1, k) - F3 (2k+1, k+1) _ (2k+1) -2k= I
and
F3 (2k+2, k) - F3 (2k+2, k+1)= (2k+3)-(2k+1)= 2
further as proved by Theorem 5
1 4-
F4 (k 2 +2, k)-F4 (k2 + 1, k) - 2 l k .
The situation is similar for d>4 .
We call attention to the following problems, left open in this paper :
PROBLEM 1 . Is the graph of Theorem 1 extremal in the sense that among all
graphs with n vertices and not containing any cycle of length 4 does it have the
maximal number of edges? (We have proved only that it is asymptotically extremal .)
We can prove the following result, which is connected with Problem 1 .
THEOREM 6 . If G„ is a graph in which any two points are connected by a path
of length 2 and which does not contain any cycle of length 4, then n=2k+ 1 and
G„ consists of k triangles which have one common
vertex (see Fig . 13) .
PROOF OF THEOREM 6 . Let G„ be a graph
with the required properties . Let P, be a point of
G„ having maximal valency . If P I is connected with
all the remaining points of G„ then evidently these
have to be connected by pairs, and G„ is of the
type described in Theorem 6 . Thus we may suppose
that G„ contains at least one point P Z which is
not connected with PI . It is easy to see that in this
case V(PZ ) = V(P I ) .
As a matter of fact there is a point P3 in G„
Fig . 13 which is connected with both P I and P2 . As there
must be a path of length 2 between P I and P3
there is a point P4 which is connected with both P, and P 3 . As there has to be a path
of length 2 between P2 and P3 , there is a point PS connected with both P 2 and P3 ,
which is clearly different from Pi , P2 , .P3 and P4 . Let Q 1 , Q2, . . ., Qk-2 be the
remaining points (besides P3 and P4) which are connected with Pi . Clearly P2
and P S are not among the Q, ; we have k~4 because v(P3 ) - 4-and by supposition
P, has the maximal valency .
Now from each of the points Q, there is a path of length 2 to P 2 ; thus for each
Q, (i =1, 2, . . ., k -2) there exists a point R, which is connected with both Q, and P 2 .
Clearly R, R; if i j because otherwise G„ would contain the cycle P I Q,R,Q j .
Further R, is different from P3 because if R, would be identical with P3 G„ would
contain the cycle P I Q,P3 P4 . Finally R, is different from P s because otherwise G„

Studia Seientiarum Mathematicarum Hungarica 1 (1966)

 ON A PROBLEM OF GRAPH THEORY 235

would contain the cycle P l Q iP 5 P3 . Thus v(P,)--k and as k=V(G,) we obtain

v(PZ)=k=v(P,) . Thus any point of G„ which is not connected with P l has the va-
lency k = v (P,) . Repeating the same argument with P 2 instead of P i it follows that
v (Q i) = k (i = l, 2, . . . , k - 2) . As P 3 is not connected with Q I (because otherwise G„
would contain the cycle P 1 Q 1 P3 P 4 ) repeating the same argument for Q instead of
P l it follows that v(P3 )=k . Thus the graph G;, is regular .
Now if V(P) =k (i=1,2, . . ., n) and G„ does not contain a cycle of length 4
and between any two points there is a path of length 2, then clearly if S i denotes
the set of points connected with P i then the sets S i and SI have exactly one point
in common, and for any two points P i and P; (j i) there is exactly one point P,,
such that S,, contains both P i and P, . Thus if we define the sets of points S i as lines
we obtain a finite plane geometry, with k=P-I-1 points on a line, and thus having
n = P Z -I- P + 1 points . But then in this geometry there would exist a one-to-one
mapping beween points and lines such that no line contains the point corresponding
to it, and such a mapping is known [5] to be impossible . This proves Theorem 6 .
PROBLEM 2 . To determine the exact value of FZ (n, k) for k < 2 , or at least
the asymptotic value of FZ (n, [nc]) with 0 < c < 2 .
PROBLEM 3 . Is the lower estimate in Theorem 3 asymptotically best possible,
I
i .e . do there exist for each d --3 a sequence of graphs G„ (n ~) with V(G.) = k - cna - I
z
where c 0 is a constant, D (Gn) = d and E(Gn) - ka-
n r cn ?
PROBLEM 4 . Determine asymptotically F4 (k 2 -I- 2, k) - k 2 .
Problems similar to those considered in this paper can be asked for directed
graphs . We hope to return to these problems in an other paper .

(Received February 1, 1966 .)

REFERENCES

[11 ERDŐS, P .-RÉNYI, A . : On a problem in the theory of graphs (in Hungarian, with English and
Russian summaries), Publ. Math. Inst . Hung . Acad. Sci. 7/ A (1962) 623-641 .
[21 ERD6s, P . : On sequences of integers no one of which divides the product of two others and
on some related problems, Mitteilangen des Forschungsinstitutes fúr Math . and Mecha-
nik, Tomsk, 2 (1938) 74-82.
[31 REIMAN, L : Über ein Problem von K . Zarankiewicz, Acta Math . Acad. Sci. Hung . 9 (1958)
269-278 .
[41 HOFFMAN, A . J .-SINGLETON, R . R . : On Moore graphs with diameter 2 and 3, IBM Journal
of Research and Development 4 (1960) 497-504 .
151 BAER, R . : Polarities in finite projective planes, Bulletin of the American Math . Soc . 52 (1946)
77-93 .

Studia Sciertiarum Mathei?zaticaricm Hunga .rica 1 (1966)