Size of Regular Graph in terms of Degree and Order

Theorem

Let $G = \struct {V, E}$ be an $r$-regular graph of order $p$.

Let $q$ denote the size of $G$.

Then:

$q = \dfrac {p r} 2$

when such an $r$-regular graph exists.

If an $r$-regular graph of order $p$ does exist, then $p r$ is an even integer.

Proof

Let $G$ be of order $p$, size $q$ and $r$-regular.

Then by definition $G$ has:

$p$ vertices each of which is of degree $r$.

$q$ edges.

Thus:

\(\ds q\)

\(=\)

\(\ds \dfrac 1 2 \sum_{v \mathop \in V} \map \deg v\)

Handshake Lemma

\(\ds \)

\(=\)

\(\ds \dfrac 1 2 \sum_{v \mathop \in V} r\)

Definition of Regular Graph

\(\ds \)

\(=\)

\(\ds \dfrac 1 2 p r\)

Definition of Order of Graph

If $p r$ is odd, that means $p$ is odd and $r$ is odd.

That means there is an odd number of odd vertices.

From the corollary to the Handshake Lemma, this is not possible

Thus for $G$ to exist, it is necessary for $p r$ to be even.

The result follows.

$\blacksquare$

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.1$: The Degree of a Vertex: Problem $9$