Plena grafeo

Ŝablono:Grafeoteorio En grafeoteorio, plena grafeo estas simpla grafeo, en kiu ĉiun paron de malsamaj verticoj konektas eĝo.

La plena grafeo de n verticoj havas $\frac{n (n - 1)}{2}$ eĝojn, kaj signiĝas per K_n. Ĝi estas regula grafeo de grado (n-1). Ĉiu plena grafeo estas kliko. Plenaj grafeoj estas maksimume koneksa ĉar la unusola vertica tranĉo kiu povas disigi la grafeon estas la tuta aro de verticoj.

Plena grafeo de n verticoj havas $n!$ aŭtomorfiojn kie la signo "!" signifas faktorialon.

Plena grafeo kun n verticoj prezentas la verticojn kaj eĝo de (n-1)-simplaĵo. Tiel K₃ respektivas al triangulo, K₄ respektivas al kvaredro, K₅ respektivas al kvinĉelo, kaj tiel plu.

K₁ ĝis K₄ estas ebenaj grafeo. Teoremo de Kuratowski asertas, ke ebena grafeo ne povas enhavi parton K₅ (aŭ la plenan dukoloran grafeon K_{3, 3}) kiel minoro. Pro tio ke K_n inkluzivas K_n-1, plena grafeo K_n kun n > 4 ne esta ebena.