Graphinvarianten-Training

Beweise für jeden endlichen ungerichteten Graphen die Formel $\sum_v\deg(v)=2|E|$.

Kann ein endlicher ungerichteter Graph genau drei Knoten ungeraden Grades besitzen?

Ein geschlossener Weg beginnt und endet in derselben von zwei Regionen eines Graphen. Zeige, dass er die Kanten zwischen den Regionen gerade oft benutzt.

Ein zusammenhängender Graph soll in einem Zug gezeichnet werden, wobei jede Kante genau einmal benutzt wird. Zeige, dass höchstens zwei Knoten ungeraden Grades haben dürfen.

Für eine Knotenmenge $S$ sei $\delta(S)$ die Menge der Kanten mit genau einem Ende in $S$. Beweise $|\delta(S)|\equiv\sum_{v\in S}\deg(v)\pmod2$.

In einem bipartiten Graphen mit Klassen $A$ und $B$ verbindet ein Weg zwei Knoten aus $A$. Zeige, dass seine Länge gerade ist.

Zeige, dass ein bipartiter Graph keinen Zyklus ungerader Länge enthalten kann.

Ein Schüler folgert aus „alle Zyklen sind gerade“, dass jeder beliebige Graph zweifärbbar sei. Korrigiere die Aussage und skizziere den Beweis der richtigen Umkehrung.