A set of topological invariants for graphs. (Q559380)

In der Ableitung der \textit{Birkhoff}schen Formel für die Anzahl \(M(\lambda )\) der Färbungen eines Graphen \(G\) mit \(\lambda \) Farben, bei denen benachbarte Knotenpunkte verschieden gefärbt sind, treten nach Verf. (A logical expansion in mathematics, Bulletin A. M. S. 38 (1932), 572-579; F. d. M. 58) als Koeffizienten der Potenzen von \(\lambda \) in \(M(\lambda )\) Zahlen \[ m_i=\sum \limits _j(-1)^{i+j}m_{ij} \] auf, mit folgender Bedeutung: \(m_{ij}\) ist die Anzahl des Teilgraphen von \(G\) vom Range \(i\) und der Nullität \(j, m_i\) die Anzahl der Teilgraphen, die keinen unvollständigen Kreis ganz enthalten (vgl. hierzu das Referat über die oben angegebene Arbeit). Hier betrachtet Verf. ähnliche Bildungen, nämlich \[ p_i=\sum \limits _j(-1)^{i+j}m_{R-j,N-i} \] (\(R\)=Rang, \(N\)=Nullität von \(G\)). Besitzt \(G\) einen dualen Graphen \(G'\) (vgl. Verf., Non-separable and planar graphs, Transactions A. M. S. 34 (1932), 339-362; F. d. M. 58), so ist \(p_i=m_i'\), wo \(m_i'\) für \(G'\) dieselbe Bedeutung hat wie \(m_i\) für \(G\). In diesem Fall erkennt man unmittelbar die topologische Invarianz der \(p_i\) daraus, daß\ bei Unterteilung von \(G\) in \(G'\) nur schon vorhandene Kanten verdoppelt werden, die Anzahl der zulässigen Färbungen von \(G'\) (für jedes \(\lambda \)) also ungeändert bleibt. Doch kann man die Invarianz der \(p_i\) leicht auch direkt, und ohne die Voraussetzung der Existenz des dualen Graphen, beweisen. Die \(p_i\) lassen eine - zur Deutung der \(m_i\) duale - Deutung zu: Nennt man eine Menge von Kanten von \(G\) eine trennende Kantenmenge (cut set of arcs), wenn bei Herausnahme dieser Kantenmenge - aber keiner echten Teilmenge davon - die Anzahl der zusammenhängenden Bestandteile von \(G\) sich vergrößert, bildet man ferner durch Weglassen je einer Kante, mit bestimmten Anordnungsvorschriften, die unvollständigen trennenden Kantenmengen (broken cut sets of arcs), so ist \((-1)^ip_i\) die Anzahl der Teilgraphen von \(G\), die keine unvollständige trennende Kantenmenge ganz enthalten.