Täisgraaf

Täisgraaf on graaf, kus iga kahe erineva tipu vahel on üks serv. Täisgraafil tippude arvuga $n$ on $n(n-1)/2$ serva ning on tähistatav $K_n$.

Täisgraafid tippude arvuga 1 kuni 8:

• 
  K₁
• 
  K₂
• 
  K₃
• 
  K₄
• 
  K₅
• 
  K₆
• 
  K₇
• 
  K₈

Täisgraaf on regulaarne valentsusega $n-1$, tugevregulaarne, transitiivne ja täissümmeetriline. Automorfismide arv $n!$. Täigraafi täiend on tühigraaf.

Graafid $K_1$ kuni $K_4$ on tasandilised. Suure tippude arvuga täisgraafid ei ole tasandilised, sest need sisaldavad alamgraafi $K_5$, mis ei rahulda Pontrjagini-Kuratovski tingimust.

Kirjandust

• Buldas, A., Laud, P., Villemson, J. (2003), Graafid, TÜ kirjastus