📂Graph Theory

Infinite Graph

Definitions ¹

1. If the vertex set $V(G)$ or the edge set $E(G)$ of a graph $G$ is an infinite set, then $G$ is called an infinite graph.
2. An infinite graph $G$, whose $V(G)$ and $E(G)$ are both countable sets, is called a Countable Graph.
3. Let’s define $A(v)$ for a vertex $v \in V(G)$ of an infinite graph $G$ as follows. $$ A(v) := \left\{ w : vw \in E(G) \right\} $$ The degree of a vertex in an infinite graph $G$ is defined as the cardinality of $A(v)$. $$ \deg (v) = | A(v) | $$ If $\deg (v) < \infty$, it is finite degree; if $\deg (v) = \aleph_{0}$, it is countable degree.
4. If all vertices of an infinite graph $G$ have finite degrees, it is said to be locally finite.
5. If all vertices of an infinite graph $G$ have countable degrees, it is said to be locally countable.

---

• Aleph $\aleph_{0}$ refers to the cardinality of a countable set.

Explanation

Infinite graphs may seem hard to imagine at first, but mathematically, they are just a natural generalization. For example, imagine a graph whose vertices are the set of integers $\mathbb{Z}$. If it is defined that whenever $v,w \in V(G) = \mathbb{Z}$, $vw \in E(G)$, there is no shortfall in calling it a graph. Naturally, this graph is an infinite graph, and particularly, it is a countable graph.