Grafo oso

Grafo teorian, grafo osoa erpin guztiak ertzen bidez konektatuta dituen grafo sinplea da.

Grafo oso
K7, 7 erpineko grafo osoa.
Erpinak	n
Ertzak	n (n-1)/2
Diametroa	1
Gerria	3, n ≥ 3 bada
Automorfismoak	n! (Sn)
Zenbaki kromatikoa	n
Indize kromatikoa	n, n bakoitia bada n-1, n bikoitia bada
Propietateak	(n-1)-erregularra Simetrikoa Erpin iragankorra Ertz iragankorra Distantzia unitatea Biziki erregularra Integrala

${\displaystyle n}$ erpineko grafo oso batek ${\displaystyle n(n-1)/2}$ ertz ditu, eta ${\displaystyle K_{n}}$ notazioaz adierazten da. Bere erpin guztiek ${\displaystyle (n-1)}$ gradua dutenez grafo erregularra da.

Kuratowski-ren teoremaren arabera, grafo lau batek ezin du ${\displaystyle K_{5}}$ grafo osoa (edo ${\displaystyle K_{3,3}}$ zatibiko grafo osoa) bere baitan izan. ${\displaystyle K_{n}}$ grafoek ${\displaystyle K_{n-1}}$ bere baitan dutenez, grafo osoa ezin da laua izan ${\displaystyle n}$${\displaystyle \geq }$${\displaystyle 5}$ balioetarako.