Vertices in Locally Finite Graph

Theorem

Then if $G$ is infinite, it contains an infinite number of vertices.

Suppose $G = \struct {V, E}$ has a finite number of vertices.

Let $V = \set {v_1, v_2, \ldots, v_n}$ where $n = \card V$ is the cardinality of $V$.

As $G$ is locally finite, each element of $V$ has a finite number of incident edges.

For each $v_k \in V$, let $r_k$ be the degree of $v_k$.

Then:

$\ds \card E \le \sum_{i \mathop = 1}^n r_k$

where $\card E$ is the cardinality of $E$, that is, the number of edges in $G$.

As $\ds \sum_{i \mathop = 1}^n r_k$ is the sum of a finite number of finite numbers, it is itself finite.

So $\card E$ is itself finite, and so $G$ has:

a finite number of edges

and so is by definition a finite graph.

By transposition, if $G$ is infinite, it must contain an infinite number of vertices.

$\blacksquare$

If $G$ is not locally finite, then in order to have a finite number of vertices and an infinite number of edges, it needs to be a multigraph.