Hallo sonnenblume,
a) Die maximale Anzahl \(c_n\) der Kanten in einem ungerichteten Graphen mit \(n\) Knoten ist $$c_n = { n \choose 2} = \frac 12 n(n-1)$$färbt man eine Anzahl \(k\) dieser Knoten mit einer anderen Farbe, so sind z.B. \(k\) Knoten rot und \(n-k\) Knoten schwarz. Die Anzahl \(c_k\) der Kanten, die zwei rote Knoten verbinden ist $$c_k = {k \choose 2}$$ und die Anzahl \(c_{n-k}\) der Kanten, die zwei schwarze Knoten verbinden ist $$c_{n-k} = { n-k \choose 2}$$bleiben noch die Kanten, die einen roten mit einem schwarzen Knoten verbinden. Ist jeder scharze Knoten mit jedem roten Knoten verbunden, so ist die Anzahl \(c_*\) dieser Kanten zwangsläufig $$c_* = n(n-k)$$Alles zusammen gefasst gibt $$\begin{aligned} c_n &= c_k + c_* + c_{n-k} \\ { n \choose 2} &= {k \choose 2} + n(n-k) + {n-k \choose 2} \\ &\text{q.e.d.}\end{aligned}$$
b) geht genauso. Betrachte die Anzahl der Kanten eines ungerichteten Graphen mit \(n\) Knoten. Die Knoten sind mit \(k\) unterschiedlichen Farben eingefärbt. Von jeder Farbe \(i\) existieren \(l_i\) Knoten.
Dann ist zwangsläufig die Summe aller Kanten gleich oder größer als die Summe aller Kanten zwischen Knoten gleicher Farbe.
Gruß Werner
