Täisgraaf
Täisgraaf on graaf, kus iga kahe erineva tipu vahel on üks serv. Täisgraafil tippude arvuga n {\displaystyle n} on n ( n − 1 ) / 2 {\displaystyle n(n-1)/2} serva ning on tähistatav K n {\displaystyle K_{n}} . Täisgraafid tippude arvuga 1 kuni 8: K1 K2 K3 K4 K5 K6 K7 K8 Täisgraaf on regulaarne valentsusega n − 1 {\displaystyle n-1} , tugevregulaarne, transitiivne ja täissümmeetriline. Automorfismide arv n ! {\displaystyle n!} . Täigraafi täiend on tühigraaf. Graafid K 1 {\displaystyle K_{1}} kuni K 4 {\displaystyle K_{4}} on tasandilised. Suure tippude arvuga täisgraafid ei ole tasandilised, sest need sisaldavad alamgraafi K 5 {\displaystyle K_{5}} , mis ei rahulda Pontrjagini-Kuratovski tingimust.