Sudost line grafů
Úloha číslo: 3632
Ukažte, že je-li graf \(G\) eulerovský, pak je jeho line graf též eulerovský.
Platí i obrácená implikace?
Line graf \(L(G)\) má za vrcholy hrany \(G\) a dva vrcholy v \(L(G)\) reprezentující hrany \(e\) a \(f\) spolu sousedí právě když \(e\) a \(f\) mají společný vrchol.
Řešení
Souvislost se v line grafu zachovává, protože vede-li mezi libovolnými vrcholy \(G\) cesta (jako posloupnost vrcholů), lze pro předepsané hrany \(e\) a \(f\) najít cestu z jednoho koncového vrcholu \(e\) do jednoho z koncových vrcholů \(f\).
Tato cesta, vnímaná jako posloupnost hran v \(G\) je cestou, vnímanou jako posloupnost vrcholů v \(L(G)\).
Spočítáme-li hrany sdílející alespoň jeden vrchol s hranou \(e=(u,v)\) v \(G\), potom dostaneme \(deg_{L(G)}(e)=deg_G(u)+\deg_G(v)-2\) což je sudé číslo za předpokladu, že \(G\) je eulerovský.
Obrácená implikace neplatí, např. linegraf \(L(K_4)\) je čtyřregulární a tudíž i eulerovský, zatímco \(K_4\) eulerovský není.