Bäume Graphen: Durchmesser

Question

Aufgabe 1: Durchmesser
a) Zeigen Sie, dass für jeden nicht zusammenhangenden Graphen G der Durchmesser
des Komplementärgraphen G' höchstens 2 ist.

b) Zeigen Sie, dass fur jeden Graphen G, dessen Durchmesser größer als 2 ist, der
Durchmesser des Komplementärgraphen G' höchstens 3 ist.

Answer 1

Ich kann hier nur a) beantworten

Aufgabe 1: Durchmesser 
a) Zeigen Sie, dass für jeden nicht zusammenhängenden Graphen G der Durchmesser 
des Komplementärgraphen G' höchstens 2 ist. 

Zu zeigen ist, dass jeder Knoten über höchstens 2 Kanten von G' erreichbar ist.
Seien A und B zwei Knoten der Graphen.

Fall A und B liegen auf nichtzusammenhängenden Teilen von G. In dem Fall sind sie in G' mit einer Kante verbunden.
 

Fall A und B liegen auf einem zusammenhängenden Teil von G.
Nun gibt es nach Voraussetzung (G nicht zusammenhängend) in G einen Knoten C, der nicht auf diesem Teil von G liegt. Die Kanten AC und CB liegen in G' und man gelangt in G' in 2 Schritten von A über C nach B.

Also: 2 Schritte genügen auf jeden Fall. qed: Durchmesser von G' ist höchstens 2.

Comments

Vielen Dank für dein Ansatz.......

du hast mir ein roten Faden für b gegeben

---

jup, danke lu, bist der beste

zu b:

Durchmesser des graphen >=3

z.z. jeder knoten in G' über <=3 kanten zu erreichen

Seien A und B ∈ V von G

1. Fall

A und B in G mit 1 Kante verbunden

==> A und B in G' mit 2 kanten verbunden

2. Fall

A und B in G über C mit 2 kanten verbunden (zur veranschauung: A-C-B)

==> A und B in G' mit 1 kante verbunden

3. Fall

Hier bin ich mir nicht ganz sicher, als einziges beispiel ist mir nur ein graph mit 4 knoten und 3 kanten eingefallen; also quasi eine ausnahme des 1. falls? (zur veranschauung: C-A-B-D)

==> A und B sind in G' mit 3 Kanten verbunden

 

Also: durchmesser von G' <=3