-
An infinite graph
consists of an infinite set of vertices and an infinite family of edges. -
A countable graph is an infinite graph where both the edge set and the vertex set are countable.
-
A locally countable graph is an infinite graph where the degree of each vertex is countable.
- That is, the set of edges incident to any vertex
is a countable set.
- That is, the set of edges incident to any vertex
-
A locally finite graph is an infinite graph where the degree of each vertex is finite.
- That is, the set of edges incident to any vertex
is finite.
- That is, the set of edges incident to any vertex
-
(Wilson 16.1) Every connected locally countable infinite graph is a countable graph
-
(Wilson 16.2) Every connected locally finite graph is a countable graph.
-
(Wilson 16.4) If
is a countable graph, every finite subgraph of which is planar, then is planar.
Traversals
-
A one-way infinite walk is of the form
such that of
and and each edge is incident to the vertices to its left and right in the sequence (i.e., ). -
A two-way infinite walk is of the form
such that of
and and each edge is incident to the vertices to its left and right in the sequence (i.e., ). -
An Eulerian Line generalizes Eulerian trails to infinite graphs. It is a two-way infinite path that traverses each edge.
-
An Eulerian Infinite Graph is an infinite graph wherein there exists an Eulerian Line in the graph
-
Konig’s Infinity Lemma
Let
be a connected locally finite infinite graph. For any vertex
, there exists a one-way infinite path with initial vertex -
For each vertex
, there is a non-trivial -path. It follows there are infinitely many paths in with initial vertex . Since the degree of
is finite, infinitely many of these paths must start with the same edge. If is such an edge, then we can repeat the procedure to get the one-way infinite path we want
-
-
(Wilson 16.4, Wilson 16.6) Let
be a connected countable graph. is Eulerian if and only if all of the following hold. has no vertices of odd degree. - For each finite subgraph
, the infinite graph obtained by performing the edge division has at most two infinite connected components - If, in addition, each vertex of
has even degree, then has exactly one infinite connected component.