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 oft 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 ableiten. Beispielsweise ist jeder unendliche planare Graph vierfärbbar, weil dies für jeden endlichen planaren Graphen gilt. Dies beruht auf dem Lemma von König.

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