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.
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.)
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.
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 )