Übung

1. Übung Graphentheorie
WS2016/17
1. Schreiben Sie für jede Ecke der folgenden 7 Graphen den Grad auf! Welche der Graphen
sind regulär?
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
G1
✉
✉
✉
G2
✉
✉
✉
✉
G3
✉
✉
G4
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
✉
G5
G6
✉
✉
G7
2. Bestimmen Sie alle paarweise nicht-isomorphen ungerichteten Graphen mit
(a) p = 2 Ecken und q = 2 bzw. q = 3 Kanten,
(b) p = 3 Ecken und q = 1, 2, 3 Kanten,
Welche der Graphen sind schlicht?
3. Bestimmen Sie alle paarweise nicht-isomorphen ungerichteten schlichten Graphen mit
(a) p = 6 Ecken, die 2-regulär bzw. 3-regulär sind,
(b) p = 4 Ecken e1 , e2 , e3 , e4 mit grad e1 = 1 grad e2 = grad e3 = 2, grad e3 = 3, bzw. mit
grad e1 = grad e2 = 2, grad e3 = grad e3 = 3.
4. Bestimmen Sie alle paarweise nicht-isomorphen ungerichteten Graphen mit p Ecken und
q Kanten und p + q ≤ 6. Welche der Graphen sind schlicht?
(3 Punkte)
5. Untersuchen Sie, welche der 7 Graphen aus Aufgabe 1 zueinander isomorph sind! (Begründung erforderlich. )
(3 Punkte)
6. Auf einer Party befinden sich 31 Personen, und jede dieser Personen kennt genau 5 andere
der anwesenden Personen. Ist das möglich?
7. Sei G ein Graph mit p Ecken und q Kanten. Zeigen Sie:
2q 2q
= max{n ∈ ZZ; n ≤ }, dann gibt es mindestens eine Ecke mit Grad
p
p
größer oder gleich m.
(a) Ist m :=
(b) Ist q = p − 1, dann existiert eine Ecke e mit grad e ≤ 1.
(c) l der Ecken sollen den Grad k haben und die restlichen Grad k + 1. Bestimmen Sie
l in Abhängigkeit von p, q und k.
8. Sei G ein Graph mit mindestens 6 Ecken. Zeigen Sie: Es gibt stets 3 Ecken, die paarweise
benachbart sind, oder 3, die paarweise nicht benachbart sind.
(3 Punkte)
9. Sei G ein schlichter Graph mit p ≥ 2 Ecken und q Kanten. Zeigen Sie:
(a) ∆(G) − δ(G) ≤ p − 2.
(b) Es gibt zwei Ecken mit gleichem Grad.
(3 Punkte)
10. (a) Bestimmen Sie einen 4-regulären schlichten Graph mit minimaler Eckenzahl p.
(b) Ist k ∈ IN ungerade, G ein k-regulärer schlichter Graph mit p Ecken und q Kanten.
Zeigen Sie: Dann ist p eine gerade Zahl und q ein ganzzahliges Vielfaches von k.
Abgabe der Aufgaben 4, 5, 8, 9 bis 29.10. vor der Vorlesung.

Download Report