Doplňky stromů
Úloha číslo: 4086
Najděte všechny stromy \(T\), jejichž doplňkem je také strom. Zdůvodněte, že jste na žádný nezapomněli.
Řešení
Protože pro \(n=|V_T|\) platí \(n=|E_T|+1=|E_{\bar T}|+1\) a \(|E_T|+|E_{\bar T}|=\binom{n}2\), musí \(n\) splňovat \(2n-2=\frac12(n^2-n)\), tedy \(n^2-5n+4=0\). Tato kvadratická rovnice má dvě nezáporná celočíselná řešení:
- \(n=1\), odpovídající strom je \(K_1\) a
- \(n=4\), odpovídající strom je \(P_4\). Ostatní stromy na čtyřech vrcholech nevyhovují, jak zjistíme rozborem případů.