Graphentheorie: 2 Kreise mit 1 gemeinsamen Kante. Zeige, dass es auch ohne die gemeinsame Kante immer einen Kreis gibt.

Question

Hi, habe ein Problem mit folgender Aufgabe. Ich verstehe die Frage und ich weiß auch, wieso es immer einen Kreis gibt ohne die Kante {x,y}. Nur wie ich das niederschreiben soll ist mir völlig unklar. An einem Beispiel mit Konkreter Kantenanzahl wäre das relativ einfach. Dort würde ich einfach die Verbleibenden Kanten aufschreiben die man abgehen muss um einen Kreis zu erhalten.

Aufgabe:
Sei G ein Graph und C1, C2 Kreise in G, die beide eine bestimmte Kante {x,y} Element E enthalten.

Außerdem sind die einzigen Knoten, die sowohl von C1 als auch von C2 durchlaufen werden x und y.

Zeigen sie, dass es dann immer auch einen Kreis in G gibt, der die Kante {x,y} nicht enthält.

Comments

Zwei Fragen:

1. Verstehst du das auch so: Man nimmt {x,y} raus und der Rest, der von C1 und C2 übrig bleibt, bildet einen Kreis?

2. Ist E die Menge der Kanten?

Answer 1

Sind C1 und C2 als Kantenmengen zu verstehen? Dann könntest du doch schreiben, dass C = C1 u C2 \ {(x,y)} der gesuchte Kreis ist.