2 Souvislost grafů Pokud máme graf, který modeluje nějaká spojení či síť, přirozeně nás zajímá, jakou máme možnost se dostat odněkud někam v tomto grafu. To má množství praktických motivací -například počítačové, dopravní, telefonní či potrubní sítě. Je pochopitelné, že v takových sítích chceme mít možnost se dostat z každého místa do každého jiného. Grafům s takovou vlastností říkáme souvislé. Fl M MAOIO "Grafy" : Souvislost grafu 2 Souvislost grafů Pokud máme graf, který modeluje nějaká spojení či síť, přirozeně nás zajímá, jakou máme možnost se dostat odněkud někam v tomto grafu. To má množství praktických motivací -například počítačové, dopravní, telefonní či potrubní sítě. Je pochopitelné, že v takových sítích chceme mít možnost se dostat z každého místa do každého jiného. Grafům s takovou vlastností říkáme souvislé. Stručný přehled lekce • Definice souvislosti grafu, vrcholová / hranová, vyšší souvislost. • Algoritmus procházení grafem (souvislou komponentou). • Eulerovské grafy. Iliněný, Fl M MAOIO "Grafy" : Souvislost grafu 2.1 Spojení vrcholů, komponenty A Definice: Sledem délky n v grafu G rozumíme posloupnost vrcholů a hran v0,eí,viíe2ív2, ...,en,vn, ve které vždy hrana ej má koncové vrcholy «j^i,t>j. Sled je vlastně procházka po hranách grafu z u do v. Příkladem sledu může být průchod IP paketu internetem (včetně cyklení). iněný, Fl K MAOIO "Grafy" : Souvislost grafu 2.1 Spojení vrcholů, komponenty ^ Definice: Sledem délky n v grafu G rozumíme posloupnost vrcholů a hran v0,eí,viíe2ív2, ...,en,vn, ve které vždy hrana ej má koncové vrcholy «j^i,t>j. Sled je vlastně procházka po hranách grafu z u do v. Příkladem sledu může být průchod IP paketu internetem (včetně cyklení). Lema 2.1. Mějme relaci ~ na množině vrcholů V(G) libovolného grafu G takovou, že pro dva vrcholy u ^ v právě když existuje v G sled začínající vu a končící ve v. Pak ~ je relací ekvivalence. Důkaz. Relace ~ je reflexivní, neboť každý vrchol je spojený sám se sebou sledem délky 0. Symetrická je také, protože sled z u do v snadno obrátíme na sled z v do u. Stejně tak je ~ tranzitivní, protože dva sledy můžeme na sebe navázat v jeden. iněný, Fl K MAOIO "Grafy" : Souvislost grafu 2.1 Spojení vrcholů, komponenty Definice: Sledem délky n v grafu G rozumíme posloupnost vrcholů a hran v0,eí,viíe2ív2, ...,en,vn, ve které vždy hrana ej má koncové vrcholy «j^i,t>j. Sled je vlastně procházka po hranách grafu z u do v. Příkladem sledu může být průchod IP paketu internetem (včetně cyklení). Lema 2.1. Mějme relaci ~ na množině vrcholů V(G) libovolného grafu G takovou, že pro dva vrcholy u ^ v právě když existuje v G sled začínající vu a končící ve v. Pak ~ je relací ekvivalence. Důkaz. Relace ~ je reflexivní, neboť každý vrchol je spojený sám se sebou sledem délky 0. Symetrická je také, protože sled z u do v snadno obrátíme na sled z v do u. Stejně tak je ~ tranzitivní, protože dva sledy můžeme na sebe navázat v jeden. D Definice: Třídy ekvivalence výše popsané (Lema 2.1) relace ~ na V(G) se nazývají komponenty souvislosti grafu G. Jinak se taky komponentami souvislosti myslí podgrafy indukované na těchto třídách ekvivalence. Ilinéný, Fl MU E MA010 "Grafy": Souvislost grafu Připomeňme si, že cesta v grafu je vlastně sledem bez opakování vrcholů. Věta 2.2. Pokud mezi dvěma vrcholy grafu G existuje sled, pak mezi nimi existuje cesta. Iliněný, Fl MU Brno MA010 "Grafy": Souvislost grafu Připomeňme si, že cesta v grafu je vlastně sledem bez opakování vrcholů. Věta 2.2. Pokud mezi dvěma vrcholy grafu G existuje sled, pak mezi nimi existuje cesta. Důkaz. Nechť u = v0, e1? v1:..., eni vn = v je sled délky n mezi vrcholy u a v v G. Začneme budovat nový sled W z vrcholu wq = u, který už bude cestou: - Předpokládejme, že nový sled W už má počátek Wq, e,\, wi,..., w, (na začátku i = 0, tj. jen wq bez hran), kde wi = v j pro některé j G {0,1,..., n}. iněný, Fl K MAOIO "Grafy" : Souvislost grafu Připomeňme si, že cesta v grafu je vlastně sledem bez opakování vrcholů. ^ Věta 2.2. Pokud mezi dvěma vrcholy grafu G existuje sled, pak mezi nimi existuje cesta. Důkaz. Nechť u = v0, e1? v1:..., eni vn = v je sled délky n mezi vrcholy u a v v G. Začneme budovat nový sled W z vrcholu wq = u, který už bude cestou: - Předpokládejme, že nový sled W už má počátek Wq, e,\, wi,..., w, (na začátku i = 0, tj. jen wo bez hran), kde wi = v j pro některé j G {0,1,..., n}. - Najdeme největší index k > j takový, že v/. = Vj = wit a sled W pokračujeme krokem ... jWi = Vj = vk, ek+1, wi+1 = vk+1,.... iněný, Fl K MAOIO "Grafy": Souvislost grafu Připomeňme si, že cesta v grafu je vlastně sledem bez opakování vrcholů. Věta 2.2. Pokud mezi dvěma vrcholy grafu G existuje sled, pak mezi nimi existuje cesta. Důkaz. Nechť u = v0, e1? v1:..., eni vn = v je sled délky n mezi vrcholy u a v v G. Začneme budovat nový sled W z vrcholu wq = u, který už bude cestou: - Předpokládejme, že nový sled W už má počátek Wq, e\,wi,..., tu» (na začátku i = 0, tj. jen wo bez hran), kde wi = v j pro některé j G {0,1,..., n}. - Najdeme největší index k > j takový, že v/. = Vj = wit a sled W pokračujeme krokem ... jWi = Vj = vk, ek+1, wi+1 = vk+1,.... - Zbývá dokázat, že nový vrchol Wj+i = vk+i se ve sledu W neopakuje. Pokud by tomu ale tak bylo j takový, že v/. = Vj = wit a sled W pokračujeme krokem ... jWi = Vj = vk, ek+1, wi+1 = vk+1,.... - Zbývá dokázat, že nový vrchol Wj+i = vk+i se ve sledu W neopakuje. Pokud by tomu ale tak bylo d h *-_ yx \ --p— > --# c a®- -Ví lliněný, Fl M MAOIO "Grafy": Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / ,•;;-—*_ e -•'b Fl M MAOIO "Grafy" : Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / ,•;;-—*_ e -•'b Fl M MAOIO "Grafy" : Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / ,•;;-—*_ e -•'b Fl M MAOIO "Grafy" : Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. Fl M MAOIO "Grafy" : Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / ,•; — --•_ e Fl M MAOIO "Grafy" : Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / ,•; — --•_ e Fl M MAOIO "Grafy" : Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / ,•; — --•_ e Ihnený, H M MAOIO "Grafy" : Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / ,•; — --•_ e Ihnený, H M MAOIO "Grafy" : Souvislost grafu Neprohledané hrany jsou čárkované, prohledané hrany plnou čarou a hrany, které vedly k nalezení vrcholů, jsou tlustou čarou (tyto hrany často mívají speciální význam v aplikacích schématu algoritmu). Nalezené vrcholy se poznají podle příchozí tlusté hrany a zpracované vrcholy jsou značené dvojím kroužkem. / ,•; — --•_ e Ihnený, H M MAOIO "Grafy" : Souvislost grafu Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a. -• c -V 6 lliněný, Fl M MAOIO "Grafy": Souvislost grafu Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a. g ,__------« ] "• Ú g •;;------•' j^~> d — ,*.. e -•' j~~> d -• c -V ď lliněný, Fl M MAOIO "Grafy": Souvislost grafu Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a. 9 •=; h — ,*.. e -•' j~-^» d -• c -V & J ~"~> d j ^> d lliněný, Fl M MAOIO "Grafy" : Souvislost grafu Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a. -• c -V 6 / _•«; —«v e lliněný, Fl M MAOIO "Grafy" : Souvislost grafu Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a. -• c -V 6 / _•«; —«v e / ,•;;---•_ e j ^> d lliněný, Fl M MAOIO "Grafy" : Souvislost grafu Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a. -• c -V 6 / _•«; —«v e / ,•;;---•_ e j ^> d lliněný, Fl M MAOIO "Grafy" : Souvislost grafu Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a. -• c -V 6 / _•«; —«v e / ,•;;---•_ e j ^> d lliněný, Fl M MAOIO "Grafy" : Souvislost grafu Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a. A iněný, Fl K MAOIO "Grafy": Souvislost grafu J Příklad 2.6. Ukázka průchodu předchozím grafem do šířky z vrcholu a. -•c h g .--_.-—«,' j~"*m d -V& / _•«; —«v e / ,• = """,•.. e ■"J » d 9 ■iy l c h 6 e -ľ.\. . d 9 ň c h í ""*,* d "J » d ff í) c ft 6 e f) d ff ň c h Tímto zpracování zadaného grafu skončilo. Vidíte rozdíly tohoto průchodu proti předchozímu příkladu? D llinéný, Fl MU B MA010 Grafy": Souvislost grafu 2.3 Vyšší stupně souvislosti V síťových aplikacích nás často zajímá nejen, jestli se za normálních podmínek můžeme pohybovat mezi vrcholy/uzly, ale také, jaké spojení můžeme nalézt v případě lokálních výpadků (odolnost a redundance). Toto lze teoreticky podchytit zkoumáním "vyšších" stupňů souvislosti grafu. liněný, Fl MU Brno MA010 "Grafy": Souvislost grafu 2.3 Vyšší stupně souvislosti V síťových aplikacích nás často zajímá nejen, jestli se za normálních podmínek můžeme pohybovat mezi vrcholy/uzly, ale také, jaké spojení můžeme nalézt v případě lokálních výpadků (odolnost a redundance). Toto lze teoreticky podchytit zkoumáním "vyšších" stupňů souvislosti grafu. Definice: Graf G je hranově k-souvislý, k > 1, pokud i po odebrání libovolných k — 1 hran z G zůstane výsledný graf souvislý. něný, Fl IV MA010 "Grafy": Souvislost grafu 2.3 Vyšší stupně souvislosti V síťových aplikacích nás často zajímá nejen, jestli se za normálních podmínek můžeme pohybovat mezi vrcholy/uzly, ale také, jaké spojení můžeme nalézt v případě lokálních výpadků (odolnost a redundance). Toto lze teoreticky podchytit zkoumáním "vyšších" stupňů souvislosti grafu. Definice: Graf G je hranově k-souvislý, k > 1, pokud i po odebrání libovolných k — 1 hran z G zůstane výsledný graf souvislý. Definice: Graf G je vrcholově k-souvislý, k > 1, pokud i po odebrání libovolných k — í vrcholů z G zůstane výsledný graf souvislý. Speciálně úplný graf Kn je vrcholově (n — l)-souvislý liněný, Fl MU Brno MA010 "Grafy": Souvislost grafu 2.3 Vyšší stupně souvislosti V síťových aplikacích nás často zajímá nejen, jestli se za normálních podmínek můžeme pohybovat mezi vrcholy/uzly, ale také, jaké spojení můžeme nalézt v případě lokálních výpadků (odolnost a redundance). Toto lze teoreticky podchytit zkoumáním "vyšších" stupňů souvislosti grafu. Definice: Graf G je hranově k-souvislý, k > 1, pokud i po odebrání libovolných k — 1 hran z G zůstane výsledný graf souvislý. Definice: Graf G je vrcholově k-souvislý, k > 1, pokud i po odebrání libovolných k — í vrcholů z G zůstane výsledný graf souvislý. Speciálně úplný graf Kn je vrcholově (n — l)-souvislý Stručně řečeno, vysoká hranová souvislost znamená vysoký stupeň odolnosti sítě proti výpadkům spojení-hran, neboli síť zůstane stále dosažitelná, i když libovolných k — 1 spojení bude přerušeno. Vysoká vrcholová souvislost je mnohem silnějším pojmem, znamená totiž, že síť zůstane dosažitelná i po výpadku libovolných k — í uzlů-vrcholů (samozřejmě mimo těch vypadlých uzlů). liněný, Fl MU Brno MA010 "Grafy": Souvislost grafu # Na ilustračním obrázku má první graf vrcholovou souvislost 4 a snadno vidíme, že po odebrání tří vrcholů či hran zůstává souvislý. Z druhého grafu bychom museli odebrat nejméně 3 hrany, aby se stal nesouvislým, a proto je jeho hranová souvislost 3. Na druhou stranu však stačí odebrat 2 vrcholy, aby mezi jeho levým a pravým krajním vrcholem žádné spojení nezůstalo. (Vidíte, které dva?) něný, Fl IV MA010 "Grafy": Souvislost grafu Mengerova věta ^ Důkaz následujícího důležitého výsledku by nebyl jednoduchý při použití stávajících znalostí, proto jej ponecháme na pozdější lekce... („Toky v sítích".) Věta 2.7. Graf G je hranově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k hranově-disjunktních cest (vrcholy mohou být sdílené). Graf G je vrcholově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k disjunktních cest (různých až na ty dva spojované vrcholy). něný, Fl IV MA010 "Grafy": Souvislost grafu Mengerova věta ^ Důkaz následujícího důležitého výsledku by nebyl jednoduchý při použití stávajících znalostí, proto jej ponecháme na pozdější lekce... („Toky v sítích".) Věta 2.7. Graf G je hranově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k hranově-disjunktních cest (vrcholy mohou být sdílené). Graf G je vrcholově k-souvislý právě když mezi libovolnými dvěma vrcholy lze vést aspoň k disjunktních cest (různých až na ty dva spojované vrcholy). Věta nám vlastně říká, že stupeň souvislosti grafu se přirozeně rovná stupni redundance spojení vrcholů. Na výše uvedeném obrázku mezi každými dvěma vrcholy prvního grafu můžeme vést až 4 disjunktní cesty. U druhého grafu třeba mezi levým a pravým koncem lze vést jen 2 (vrcholově) disjunktní cesty, ale mezi každými dvěma vrcholy lze vést 3 hranově-disjunktní cesty. něný, Fl IV MA010 "Grafy": Souvislost grafu V duchu předchozí Mengerovy věty pokračujeme s následujícími poznatky. Věta 2.8. Nechť G je vrcholově 2-souvislý graf. Pak každé dvě hrany v G leží na společné kružnici. liněný, Fl MU Brno MA010 "Grafy": Souvislost grafu V duchu předchozí Mengerovy věty pokračujeme s následujícími poznatky. ^ Věta 2.8. Nechť G je vrcholově 2-souvislý graf. Pak každé dvě hrany v G leží na společné kružnici. Důkaz: Nechť e, / G E(G). Sestrojíme graf G' podrozdělením obou hran e, / novými vrcholy ve,Vf. Je zřejmé, že i G' je vrcholově 2-souvislý graf, takže podle Věty 2.7 existují v G' dvě disjunktní cesty spojující ve s vj, tvořící spolu kružnici C'. Nakonec C indukuje v G kružnici C procházející e i /. něný, Fl IV MA010 "Grafy": Souvislost grafu V duchu předchozí Mengerovy věty pokračujeme s následujícími poznatky. ^ Věta 2.8. Nechť G je vrcholově 2-souvislý graf. Pak každé dvě hrany v G leží na společné kružnici. Důkaz: Nechť e, / G E(G). Sestrojíme graf G' podrozdělením obou hran e, / novými vrcholy ve,Vf. Je zřejmé, že i Q' je vrcholově 2-souvislý graf, takže podle Věty 2.7 existují v G' dvě disjunktní cesty spojující ve s vj, tvořící spolu kružnici C'. Nakonec C indukuje v G kružnici C procházející e i /. D Rozšířením předchozí úvahy lze dokonce dokázat: Věta 2.9. Nechť G je vrcholově k-souvislý graf, k > 1. Pak pro každé dvě disjunktní množiny U1,U2 C V (G), \Ui\ = \U2\ = k v G existuje k zcela disjunktních cest z Vrcholů U\ do Vrcholů fu- něný, Fl IV MA010 "Grafy": Souvislost grafu 2.4 Jedním tahem: Eulerovské grafy Definice: Tah je sled v grafu bez opakování hran. Uzavřený tah je tahem, který končí ve vrcholu, ve kterém začal. Nejstarší výsledek teorie grafů vůbec pochází od Leonarda Eulera: (Slavných 7 mostů v Královci / Königsbergu / dnešním Kaliningradě. Fl M MAOIO "Grafy": Souvislost grafu 2.4 Jedním tahem: Eulerovské grafy Definice: Tah je sled v grafu bez opakování hran. Uzavřený tah je tahem, který končí ve vrcholu, ve kterém začal. Nejstarší výsledek teorie grafů vůbec pochází od Leonarda Eulera: (Slavných 7 mostů v Královci / Königsbergu / dnešním Kaliningrads.) Věta 2.10. Graf G lze nakreslit jedním uzavřeným tahem právě když G je souvislý a všechny vrcholy v G jsou sudého stupně. něný, Fl IV MA010 "Grafy": Souvislost grafu 2.4 Jedním tahem: Eulerovské grafy Definice: Tah je sled v grafu bez opakování hran. Uzavřený tah je tahem, který končí ve vrcholu, ve kterém začal. Nejstarší výsledek teorie grafů vůbec pochází od Leonarda Eulera: (Slavných 7 mostů v Královci / Königsbergu / dnešním Kaliningrads.) Věta 2.10. Graf G lze nakreslit jedním uzavřeným tahem právě když G je souvislý a všechny vrcholy v G jsou sudého stupně. Důsledek 2.11. Graf G lze nakreslit jedním otevřeným tahem právě když G je souvislý a všechny vrcholy v G až na dva jsou sudého stupně. něný, Fl IV MA010 "Grafy": Souvislost grafu Důkaz: Dokazujeme oba směry ekvivalence. A - Pokud lze G nakreslit jedním uzavřeným tahem, tak je zřejmě souvislý a navíc má každý stupeň sudý, neboť uzavřený tah každým průchodem vrcholem „ubere" dvě hrany. něný, Fl IV MA010 "Grafy": Souvislost grafu Důkaz: Dokazujeme oba směry ekvivalence. ^ - Pokud lze G nakreslit jedním uzavřeným tahem, tak je zřejmě souvislý a navíc má každý stupeň sudý, neboť uzavřený tah každým průchodem vrcholem „ubere" dvě hrany. - Naopak zvolíme mezi všemi uzavřenými tahy T m G ten (jeden z) nejdelší. Tvrdíme, že T obsahuje všechny hrany grafu G. - Pro spor vezměme graf G' = G — E (T), o kterém předpokládejme, že je neprázdný. Jelikož G" má taktéž všechny stupně sudé, je (z indukčního předpokladu) nakreslený jedním uzavřeným tahem T'. něný, Fl IV MA010 "Grafy": Souvislost grafu Důkaz: Dokazujeme oba směry ekvivalence. ^ - Pokud lze G nakreslit jedním uzavřeným tahem, tak je zřejmě souvislý a navíc má každý stupeň sudý, neboť uzavřený tah každým průchodem vrcholem „ubere" dvě hrany. - Naopak zvolíme mezi všemi uzavřenými tahy T m G ten (jeden z) nejdelší. Tvrdíme, že T obsahuje všechny hrany grafu G. - Pro spor vezměme graf G' = G — E (T), o kterém předpokládejme, že je neprázdný. Jelikož G" má taktéž všechny stupně sudé, je (z indukčního předpokladu) nakreslený jedním uzavřeným tahem T'. - Vzhledem k souvislosti G existuje vrchol w incidentní zároveň s hranami T i T', tudíž lze oba tahy T a T' „spojit přes w". To je spor s předpokladem. něný, Fl IV MA010 "Grafy": Souvislost grafu Důkaz: Dokazujeme oba směry ekvivalence. - Pokud lze G nakreslit jedním uzavřeným tahem, tak je zřejmě souvislý a navíc má každý stupeň sudý, neboť uzavřený tah každým průchodem vrcholem „ubere" dvě hrany. - Naopak zvolíme mezi všemi uzavřenými tahy T m G ten (jeden z) nejdelší. Tvrdíme, že T obsahuje všechny hrany grafu G. - Pro spor vezměme graf G' = G — E (T), o kterém předpokládejme, že je neprázdný. Jelikož G" má taktéž všechny stupně sudé, je (z indukčního předpokladu) nakreslený jedním uzavřeným tahem T'. - Vzhledem k souvislosti G existuje vrchol w incidentní zároveň s hranami T i T', tudíž lze oba tahy T a T' „spojit přes w". To je spor s předpokladem. D Důkaz důsledku: Nechť u,v jsou dva vrcholy grafu G mající lichý stupeň, neboli dva (předpokládané) konce otevřeného tahu pro G. Do G nyní přidáme nový vrchol w spojený hranami s u a v. Tím jsme náš případ převedli na předchozí případ grafu se všemi sudými stupni. D Fl MU Brno MA010 "Grafy": Souvislost grafu