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í.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze