Infinite graph

In graph theory, an infinite graph is a graph whose number of nodes or edges is infinite. If, on the other hand, one speaks of a graph, it is often assumed that the number of nodes and edges are finite. A graph is called wegendlich referred if he, despite potentially infinite number of nodes, not infinitely long path has.

Statements about infinite graphs can often be derived from corresponding statements about finite graphs using a compactness argument . For example, every infinite planar graph can be four-colored because this is true for every finite planar graph. This is based on König's lemma .

Other statements are not necessarily transferable to infinite graphs.

The Cayley graph of the free group with two generators a and b

Examples

Cayley graphs of infinite groups are examples of infinite graphs with very high symmetry. (All elements of the group are symmetries of the graph.) ${\ displaystyle \ Gamma}$ ${\ displaystyle \ Gamma}$

Expander graphs are important in many internal and external mathematical applications .

Locally finite graph

A graph is called locally finite if every node has only a finite number of neighbors.

Farey graph : nodes correspond , the edge exists if

{\ displaystyle \ mathbb {Q} \ cup \ infty}

{\ displaystyle (p / q, r / s)}

{\ displaystyle | ps-rq | = 1}

Fine graphs

An important class of graphs in geometric group theory are fine graphs , they include locally finite graphs and, for example, the Farey graph .

application

In functional analysis , infinite graphs appear as so-called Bratteli diagrams when investigating AF-C * algebras .

literature

Dénes Kőnig : Theory of finite and infinite graphs. Combinatorial topology of the route complexes , Akademische Verlagsgesellschaft, Leipzig 1936
Reinhard Diestel : Infinite graphs , Chapter 8 in Reinhard Diestel: Graph theory. 4th [electronic] edition 2010. Corrected reprint 2012 , Springer, 2012, ISBN 978-3-642-14278-9 , pp. 203-268 (English; table of contents )