Wspólna krawędź

[mol_ksiazkowy]

Udowodnić, że jeśli w grafie prostym \(\displaystyle{ G}\) istnieje krawędź , która jest wspólna dla dwóch dowolnych cykli, to istnieje też cykl bez tej krawędzi.

[kerajs]

Oznaczę wierzchołki wspólnej krawędzi obu cykli przez A i B. Z A do B wiodą co najmniej trzy drogi:
1) po krawędzi między A i B
2) po pierwszym cyklu z wyłączeniem krawędzi między A i B
3) po drugim cyklu z wyłączeniem krawędzi między A i B
A skoro tak, to z A do B dojdę trasą 2), a następnie z B do A trasą 3) więc cała ta trasa z A do A tworzy trzeci cykl (który nie zawiera krawędzi AB) .

[FasolkaBernoulliego]

Stwierdzenie nie jest prawdziwe. Np. w grafie 3-wierzchołkowym pełnym G każda krawędź jest wspólna dla dowolnych dwóch cykli w G (jedyny wybór to dwa takie same cykle), natomiast nie istnieje w nim cykl nie zawierający którejkolwiek. Chyba trzeba doprecyzować?

[kerajs]

w grafie 3-wierzchołkowym pełnym G każda krawędź jest wspólna dla dowolnych dwóch cykli w G (jedyny wybór to dwa takie same cykle), natomiast nie istnieje w nim cykl nie zawierający którejkolwiek.

Dla mnie w tym grafie jest tylko jeden cykl, więc nie spełnia on założeń zadania.
Ciekami mnie, ile Ty tu widzisz cykli?

Twój post uświadomił mi pewną luką w poprzednim dowodzie. Jest on poprawny jeśli cykle rozdzielają się w wierzchołkach \(\displaystyle{ A}\) i \(\displaystyle{ B}\).

W sytuacji gdy krawędź \(\displaystyle{ AB}\) jest fragmentem wspólnej gałęzi obu cykli to:
Końcowe wierzchołki maksymalnie wspólnej (czyli takiej, poza którą cykle od razu się rozdzielają (choć mogą gdzieś dalej ponownie się połączyć i rozdzielić)) gałęzi zawierającej krawędź \(\displaystyle{ AB}\) oznaczam przez \(\displaystyle{ A'}\) i \(\displaystyle{ B'}\). Z \(\displaystyle{ A'}\) do \(\displaystyle{ B' }\) wiodą co najmniej trzy drogi:
1) po gałęzi \(\displaystyle{ A'B'}\) zawierającej krawędź między \(\displaystyle{ A}\) i \(\displaystyle{ B}\)
2) po pierwszym cyklu z wyłączeniem gałęzi między \(\displaystyle{ A'}\) i \(\displaystyle{ B'}\)
3) po drugim cyklu z wyłączeniem gałęzi między \(\displaystyle{ A'}\) i \(\displaystyle{ B'}\)
A skoro tak, to z \(\displaystyle{ A'}\) do \(\displaystyle{ B'}\) dojdę trasą 2), a następnie z \(\displaystyle{ B'}\) do \(\displaystyle{ A'}\) trasą 3) więc cała ta trasa z \(\displaystyle{ A'}\) do \(\displaystyle{ A'}\) tworzy trzeci cykl (który nie zawiera gałęzi \(\displaystyle{ A'B'}\), w tym i krawędzi \(\displaystyle{ AB}\)) .

[FasolkaBernoulliego]

Ciekami mnie, ile Ty tu widzisz cykli?

Ja też tam widzę jeden cykl, chociaż na upartego można by uznać, że jest ich 6. Natomiast w treści zadania nie jest napisane, że te dowolne cykle mają być różnymi cyklami.

Jeśli dobrze rozumiem, to tutaj się tak naprawdę dowodzi, że jeśli jest więcej niż jeden cykl, to nie istnieje krawędź wspólna dla wszystkich cykli?

[kerajs]

Ja też tam widzę jeden cykl, chociaż na upartego można by uznać, że jest ich 6.

To po co się upierać?

w treści zadania nie jest napisane, że te dowolne cykle mają być różnymi cyklami.

Skoro, niezależnie od wierzchołka startu i kierunku poruszania się, widzimy tam tylko jeden cykl, to dwa dowolne cykle są różnymi cyklami.

Jeśli dobrze rozumiem, to tutaj się tak naprawdę dowodzi, że jeśli jest więcej niż jeden cykl, to nie istnieje krawędź wspólna dla wszystkich cykli?

Nie.
Dowodzi się rzeczy trywialnej i oczywistej:
Skoro istnieją dwie różne pętle o wspólnym odcinku, to istnieje także pętla która ten odcinek pomija.

PS
Przepraszam za zwłokę w odpowiedzi.

[FasolkaBernoulliego]

Założenie zadania mówi, że istnieje krawędź, która jest wspólna dla dowolnych dwóch cykli. Pokazujesz, że jeśli faktycznie tak jest i weźmiemy jakieś dwa cykle, powiedzmy A i B, to że istnieje trzeci cykl, C, bez tej krawędzi. W takim razie ta krawędź nie jest krawędzią wspólną dla dowolnych dwóch cykli, np. dla A i C. Sprzeczność, czy ja czegoś nie rozumiem?

Jeśli chodzi o te dwa dowolne cykle, to oczywiście kwestia umowy. Pytanie czy bierzemy
\(\displaystyle{ \forall \{A,B\}}\),
czy
\(\displaystyle{ \forall A,B}\).
Ponieważ nie było sprecyzowane, więc ja zrozumiałem na drugi sposób.