[grafy]Las, którego dopełnienie jest drzewem.

[hoot1hooten]

Szanowni Państwo,
mam problem z pewnym zadaniem. Pytanie brzmi:
Na ilu wierzchołkach można zbudować las, którego dopełnienie jest drzewem?

Doszedłem do tego, że dla <5 wierzchołków jest to możliwe.

Dlaczego tak jest? Z czego to wynika?

Z góry dziękuję za pomoc i poświęcony czas.
Pozdrawiam

[Bugmenot]

• Odwrotnie - czy dopełnienie drzewa na \(\displaystyle{ n \geq 5}\) wierzchołkach tworzy las?
  
  \(\displaystyle{ |E_{K_n}| = \frac{(n-1) \cdot n}{2}}\)
  
  \(\displaystyle{ |E_T| = (n-1)}\)
  
  \(\displaystyle{ |E_{T'}| = \frac{(n-1) \cdot n}{2} - (n-1)}\)
  
  
  Dla \(\displaystyle{ n=5}\):
  
  \(\displaystyle{ |E_{K_n}| = 10}\)
  
  \(\displaystyle{ |E_T| = 4}\)
  
  \(\displaystyle{ |E_{T'}| = 6}\)
  
  Można zauważyć, że dla \(\displaystyle{ T'}\) liczba krawędzi jest większa niż liczba wierzchołków - wobec czego graf zawiera cykl i nie jest lasem.
  Dla kolejnych \(\displaystyle{ n}\) będzie tak samo. Dlatego nie istnieje takie drzewo dla \(\displaystyle{ n \geq 5}\).