UDC 519.54

MATHEMATICS

V. G. VIZING

ON THE NUMBER OF EDGES IN A GRAPH WITH GIVEN RADIUS

(Presented by Academician A. D. Aleksandrov on 20 VI 1966)

In this note the maximum number of edges in an \(n\)-vertex graph having a given radius is established. Only finite connected undirected graphs without loops and parallel edges are considered \((^{1})\).

The distance \(\rho(x,y)\) between vertices \(x\) and \(y\) is the length (the number of edges) of the shortest chain joining \(x\) and \(y\). The radius \(r(G)\) of a graph \(G\) is the greatest integer possessing the following property: whatever vertex \(x\) of the graph \(G\) is taken, there is a vertex \(y\) such that \(\rho(x,y)\ge r(G)\). The diameter \(d(G)\) of a graph \(G\) is the greatest distance between two vertices of the graph \(G\).

Obviously, \(r(G)\le d(G)\). If \(G\) is a tree, then
\[ r(G)=[(d(G)+1)/2]. \]
It follows from this, in particular, that the number of vertices in a graph is at least twice its radius.

We shall denote by \(\sigma(x)\) the degree of the vertex \(x\), and by \(\sigma(G)\) the maximum degree of a vertex of the graph \(G\).

Lemma 1. In an \(n\)-vertex graph \(G\),
\[ \sigma(G)\le n-2r(G)+2. \]

Lemma 2. Let \(G\) be an \(n\)-vertex graph with \(r(G)\ge 3\), and let \(x\) and \(y\) be vertices of \(G\) with \(\rho(x,y)\ge 3\). Then
\[ \sigma(x)+\sigma(y)\le n-2r(G)+4. \]

The proofs of Lemmas 1 and 2 are analogous.

We prove Lemma 2. Let the vertices \(x_1,x_2,\ldots,x_i\) be adjacent to the vertex \(x\), and the vertices \(y_1,y_2,\ldots,y_j\) to the vertex \(y\). Construct a tree \(T\) covering the graph \(G\) and containing the edges
\[ (x,x_1),\ldots,(x,x_i),\ (y,y_1),\ldots,(y,y_j). \]
It must be that
\[ d(T)\ge 2r(G)-1. \]
Take an elementary chain joining two most distant vertices of the tree \(T\). This chain contains no more than 6 vertices from the set
\[ x,x_1,\ldots,x_i;\ y,y_1,\ldots,y_j \]
and no fewer than \(2r(G)-6\) other vertices. Consequently,
\[ n\ge 2r(G)-6+i+1+j+1, \]
whence
\[ \sigma(x)+\sigma(y)=i+j\le n-2r(G)+4, \]
as was required to prove.

Let \(n\) and \(k\) be natural numbers and let \(n\ge 2k\ge 2\). Denote by \(f(n,k)\) the maximum number of edges that an \(n\)-vertex graph with radius \(k\) may have, and by \(C(n,k)\) an \(n\)-vertex graph with \(f(n,k)\) edges and with \(r(C(n,k))=k\). Obviously,
\[ f(n+1,k)>f(n,k) \]
and
\[ f(n,k+1)<f(n,k). \]

Theorem.
\[ f(n,1)=\frac{n(n-1)}{2},\qquad f(n,2)=\left[\frac{n(n-2)}{2}\right]; \]
for \(k\ge 3\),
\[ f(n,k)=\frac{n^2-4kn+5n+4k^2-6k}{2}. \]

Proof. The first two equalities are obvious. Now let \(k\ge 3\). For brevity denote
\[ g(n,k)=\frac{n^2-4kn+5n+4k^2-6k}{2}\qquad (n\ge 2k\ge 6). \]

We first show that \(f(n,k)\ge g(n,k)\). Indeed, let the graph \(H\) have the following structure: its vertices are
\[ a_1,a_2,\ldots,a_{2k},\ b_1,\ldots,b_{n-2k}; \]
the subgraph generated by the vertices \(a_1,a_2,\ldots,a_{2k}\) is the elementary cycle
\[ [a_1,a_2,\ldots,a_{2k},a_1]; \]
the vertices \(b_1,\ldots,b_{n-2k}\) are pairwise adjacent, and each of them is adjacent to the vertices \(a_1,a_2,a_3\). The \(n\)-vertex graph \(H\) has, obviously, \(g(n,k)\) edges and \(r(H)=k\). This proves the required inequality.

We shall prove the inequality \(f(n,k) \leqslant g(n,k)\) by double induction on \(n\) and \(k\).

Basis of the induction:

1) \(f(n,3) \leqslant g(n,3)\) for every \(n \geqslant 6\).

2) \(f(2k,k) \leqslant g(2k,k)\) for every \(k \geqslant 3\).

1) It is not difficult to verify that in the graph \(C(n,3)\) one can always indicate three nonintersecting pairs of vertices \(\{x_1,y_1\}\), \(\{x_2,y_2\}\), \(\{x_3,y_3\}\) such that \(\rho(x_i,y_i) \geqslant 3\) \((i=1,2,3)\). By Lemmas 1 and 2, then

\[ f(n,3) \leqslant \frac{[3(n-2)+(n-6)(n-4)]}{2} = \frac{(n^2-7n+18)}{2} = g(n,3). \]

2) This is obvious.

Induction step. Let \(k \geqslant 4\), \(n \geqslant 2k+1\), and suppose it has been proved that \(f(n_0,k_0) \leqslant g(n_0,k_0)\) if either \(3 \leqslant k_0 < k\), or \(k_0=k\) but \(n_0<n\). Consider the subgraph \(L\) of the graph \(C(n,k)\) generated by all vertices except one vertex \(x\) that is not a cut point. If \(r(L) \geqslant k\), then, by the induction hypothesis, the graph \(L\) contains no more than \(g(n-1,k)\) edges, and since, by Lemma 1, \(\sigma(x) \leqslant n-2k+2\), we have \(f(n,k) \leqslant g(n-1,k)+n-2k+2 = g(n,k)\).

Suppose now that any subgraph of the graph \(C(n,k)\) obtained by deleting from \(C(n,k)\) a vertex different from a cut point has radius \(k-1\). Then for every vertex \(x\) of the graph \(C(n,k)\) that is not a cut point there is a vertex \(y\) such that \(\rho(y,x)=k\), but for \(z \ne x\), \(\rho(y,z) \leqslant k-1\). We shall call the vertex \(y\) conjugate to the vertex \(x\). Obviously, if \(y\) is also not a cut point, then the vertex \(x\) is conjugate to the vertex \(y\).

Taking into account the indicated assumption on the structure of the graph \(C(n,k)\), as well as the induction hypothesis, it is not difficult to prove the validity of the inequality \(f(n,k) \leqslant g(n,k)\) in the case where the graph has at least one cut point. Therefore we shall assume that the graph \(C(n,k)\) has no cut points.

Since \(d(C(n,k)) \geqslant k\), by Menger’s theorem \((^1)\), in the graph \(C(n,k)\) there exists an elementary cycle of length \(\geqslant 2k\). Among all elementary cycles of length \(\geqslant 2k\), choose a cycle \(M_0\) of least length \(m_0 \geqslant 2k\). The cycle \(M_0\) has no chords, i.e., the subgraph generated by the vertices of the cycle \(M_0\) is an elementary cycle. Indeed, otherwise in the graph \(C(n,k)\) one could indicate a set consisting of \(2k-2\) vertices, the distance between any two of which does not exceed \(k-1\). Since to each of these vertices there is mutually uniquely conjugate some vertex of the graph \(C(n,k)\), by Lemmas 1 and 2,

\[ f(n,k) \leqslant \frac{[(2k-2)(n-2k+4)+(n-2k+2)(n-4k+4)]}{2} < g(n,k), \]

which is impossible.

Let \(x\) be a vertex not belonging to the cycle \(M_0\). If a vertex of the cycle \(M_0\) is conjugate to the vertex \(x\), then, obviously, \(x\) is adjacent to no more than \(m_0-2k+3\) vertices of the cycle \(M_0\). If, however, a vertex \(y\) not lying on the cycle \(M_0\) is conjugate to the vertex \(x\), then, having no common adjacent vertices, the vertices \(x\) and \(y\) are adjacent in total to no more than \(m_0-2k+6 \leqslant 2(m_0-2k+3)\) vertices of the cycle \(M_0\). Thus,

\[ f(n,k) \leqslant m_0+(n-m_0)(m_0-2k+3) +\frac{(n-m_0)(n-m_0-1)}{2} \leqslant g(n,k). \]

The theorem is proved.

Let us note in conclusion that for fixed \(n\) and \(k\) satisfying the conditions \(k \geqslant 3\), \(n \geqslant 2k+2\), the graphs \(C(n,k)\) need not be isomorphic.

Institute of Mathematics
Siberian Branch of the Academy of Sciences of the USSR

Received
13 VI 1966

REFERENCES

1. C. Berge, Graph Theory and Its Applications, IL, 1962.