Vertices in Locally Finite Graph

Theorem

Let $G$ be a locally finite graph.

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

Proof

Suppose $G = \left({V, E}\right)$ has a finite number of vertices.

Let $V = \left\{{v_1, v_2, \ldots, v_n}\right\}$ where $n = \left|{V}\right|$ 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:

$\displaystyle \left|{E}\right| \le \sum_{i=1}^n r_k$

where $\left|{E}\right|$ is the cardinality of $E$, that is, the number of edges in $G$.

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

So $\left|{E}\right|$ is itself finite, and so $G$ has:

a finite number of vertices

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$

Note

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.