Pogovor:Polni graf

Izrek Kuratowskega je pomemben rezultat, a za ta članek PMSM ni bistven. Če pa je že notri v obliki

»Ravninski graf ne more vsebovati $K_{5}$ (ali polnega dvodelnega grafa $K_{3,3}$) kot minorja«,

me zanima, kaj je to minor? --romanm (pogovor) 10:58, 22 oktober 2005 (CEST)

To je verjetno podgraf, torej graf kjer iz katerega so odtranjene nekatere povezave.

Ali ni to subdivizija? Sta minor in subdivizija sopomenki? Malo sem že pozabil, zvezkov pa nimam pri roki ... --romanm (pogovor) 09:57, 29 oktober 2005 (CEST)

Graf H=(U,F) je podgraf grafa G=(V,E), če je U podmnožica V in je F podmnožica E. Pozor! Pri tem je pomebno, da je (U,F) res graf! Vsaka izbira podmnožic U in F v splošnem ne določa grafa. Za vsako izbrano povezavo moramo izbrati tudi njeni krajišči.

Hvala! V tem primeru minor ne more biti samo podgraf, ali pa je čisto zgornja trditev napačna, ker izrek Kuratowskega trdi več kot to, da graf ni ravninski, če obstaja podgraf $K_{5}$ ali $K_{3,3}$. V poštev pride namreč (po spominu in z mahanjem rok) tudi odstranjevanje točk in dodelitev njihovih povezav sosedom (ali nekaj takega). --romanm (pogovor) 10:15, 29 oktober 2005 (CEST)

IZREK 1 (Kuratowski) Graf G je ravninski natanko takrat, ko ne vsebuje subdivizije K3,3 in ne subdivizije K5.

Naj bo e povezava grafa G. Naj S(G,e) označuje graf, ki ga dobimo tako, da povezavo e nadomestimo s potjo dolžine 2. Tej operaciji rečemo subdivizija povezave. Če je F podmnožica EG, bo S(G,F) oznaka za graf, ki ga dobimo s subdivizijo vseh povezav iz F. Če je F=E, bomo drugi argument opustili in bo S(G) označeval subdivizijo grafa G.