Rozklad úplného grafu na tři Petersenovy grafy

Úkol: S využitím výsledků příkladu 7.7 dokažte, že úplný graf na deseti vrcholech nelze zapsat jako sjednocení tří (disjunktních) Petersenových grafů.


Řešení: Dokazujme sporem. Předpokládejme, že $ I_1$, $ I_2$ a $ I_3$ jsou matice incidence Petersenova grafu takové, že $ I_1+I_2+I_3=J-\mathbbm{1}$, kde $ J$ je matice tvořená samými jedničkami a $ \mathbbm{1}$ je jednotková matice. Uvažme matici $ J-\mathbbm{1}-I_1-I_2$. Spektrum této matice je dle výsledků příkladu 7.7 $ \{3,\, 1,\, -2\}$. Uvažme nyní vlastní podprostor matice $ J$ odpovídající vlastnímu číslu 0. Ten obsahuje vlastní podprostory (dimenze pět) pro vlastní číslo $ 1$ jak matice $ I_1$ tak i $ I_2$. Protože je však jeho dimenze (pouze) devět, musí mít výše zmiňované vlastní podprostory matic $ I_1$ a $ I_2$ neprázdný průnik -- tedy existuje jejich společný vlastní vektor, který označíme $ \vec{v}$. Nyní již stačí provést několik jednoduchých úprav: $ I_3
\vec{v}=(J-\mathbbm{1}-I_1-I_2)\vec{v}= J\vec{v}-\mathbbm{1}\vec{v}-I_1 \vec{v}-I_2
\vec{v}= -\vec{v}-\vec{v}-\vec{v}=-3\vec{v}$. To je ale spor, neboť matice $ I_3$ nemá vlastní číslo $ -3$.

$ \ast$DK$ \ast$