Unendlicher Graph

Als unendlichen Graph bezeichnet man in der Graphentheorie einen Graphen, dessen Knoten- oder Kantenzahl unendlich ist. Spricht man hingegen von einem Graphen so wird üblicherweise angenommen, dass Knoten- und Kantenzahl endlich sind. Ein Graph wird als wegendlich bezeichnet, falls er, trotz möglicherweise unendlich vieler Knoten, keinen unendlich langen Weg besitzt.

Aussagen über unendliche Graphen lassen sich häufig mittels eines Kompaktheitsarguments aus entsprechenden Aussagen über endliche Graphen erhalten. Beispielsweise ist jeder unendliche planare Graph vierfärbbar, weil dies für jeden endlichen planaren Graphen gilt.

Andere Aussagen sind nicht zwangsläufig auf unendliche Graphen übertragbar.

Anwendung

In der Funktionalanalysis treten unendliche Graphen als sogenannte Bratteli-Diagramme bei der Untersuchung von AF-C*-Algebren auf.