Graph zusammenhängender Graph und 2- regulärer Graph

Question

Guten Mittag liebe Mathegenuis,

ich brauche eure Hilfe! Habe für diese Aufgabe leider Lösung zu Hand:

 

Leider habe ich keine Idee welche Lösung für Aufgabe b) oder c) gelten sollte.

a) Lösungen:

Ordnung = |V| = 10

Größe = |E| = 8

Anzahl Zusammenhangskomponenten = 3

Es wäre sehr nett von euch wenn mir jemand bei der b) und bei der c) helfen könnte.

Danke im Voraus und noch einen schönen Tag!

Liebe Grüße

euer Max

Answer 1

b) Du brauchst zwei neue Kanten, weil ja eine Kante maximal zwei Zusammenhangskomponenten verbinen kann. Möglichkeiten sind

• Eine Kante von einem der Knoten aus {a,b,d,f,h} zu einem der Knoten aus {c,e,g,i} und eine Kante von einem der Knoten aus {a,b,d,f,h} zu einem der Knoten aus {j,k}.
• Eine Kante von einem der Knoten aus {c,e,g,i} zu einem der Knoten aus {a,b,d,f,h} und eine Kante von einem der Knoten aus {c,e,g,i} zu einem der Knoten aus {j,k}.
• Eine Kante von einem der Knoten aus {j,k} zu einem der Knoten aus {a,b,d,f,h} und eine Kante von einem der Knoten aus {j,k} zu einem der Knoten aus {c,e,g,i}.

> Ordnung = |V| = 10 

Darüber solltest du veilleicht noch mal genau nachdenken :-)