Transcription of G V;E
1 PlanarGraphsA graphG= (V; E)isplanarif it canbe drawn ontheplanewithoutedgescrossingexceptaten dpoints :thereis a 1-1functionf:V!R2andforeache2 Ethereexistsa 1-1continuousge:[0;1]!R2suchthat(a)e=xyi mpliesf(x) =ge(0)andf(y) =ge(1).(b)e6=e0impliesthatge(x)6=ge0(x0) forallx; x02(0;1).georitsimageis referredto Theorem(F ary)A simpleplanargraphhasanembeddingin Notallgraphsareplanar. Graphscanhave several planegraphG, a faceis a maximalregionSsuchthatx; y2 Simpliesthatx; ycanbejoinedbya curve whichdoesnotmeetany edgeof embeddinghas7 theouterorinfiniteface. (G)is thenumberof a 1-1continuousmapfromthecircleS1!R2thenfp artitionsR2nf(S1)intotwo disjointcon-nectedopensetsInt(f); Ext(f). Theformeris boundedandthelatteris consequence, ifx2 Int(f); y2 Ext(f)andx; yarejoinedby a closedcurveCinR2thenCmeetsf(S1).4K5is insideoroutsideofC noplacetoputv5 we placev5intoC1thenthev5v3curve crossestheboundary graphisembeddableintheplaneiffit isembed-dable onthesurfaceof a :R2!
2 (x; y) = 2x ;2y ; 2 where = 1 +x2+ canchooseztobeany pointnotanedgeorvertex a vertex ofa planegraph,Gcanbeembeddedin theplanesothatvis (f)offacefofplanegraphGisaclosedclockwis ewalkaroundtheedgesof (f0) =e1e2e3e8e9e10e11e8e4e5b(f1) =e1e2e3e6e7e6e4e5b(f2) =e9e10e11b(f3) =e77 Thedegreed(f)offacefis thenumberofedgesinb(f).Eachedgeappearstw iceasanedgeofa boundaryandsoifFis thesetof facesofG, thenXf2Fd(f) = 2 :A cutedgelikee6appearstwicein theboundary defineitsdualG =(V ; E )asfollows:Thereis a vertexf correspond-ingto anedgee andg arejoinedby edgee iffedgeeis ontheboundary (a)G is planar.(b)GconnectedimpliesG =G:29fffffeeeeeeee01231234567849effff03f 2**1412346578910 Thefollowingispossible:start withplanargraphGandform2 distinctembeddingsG1; G2. ThedualsG 1; G 2may faceofdegree5 andsoG 1hasa vertex a (G)is thenumberof facesof planegraphG.(a) (G ) = (G).(b) (G ) = (G).(c)dG (f ) =dG(f).
3 Notethat(c)saysthatthedegreeoff inG is equalto thesize of theboundary s FormulaTheorem2 LetGbea + = 2:ProofByinductionon .If = 1thenGis a collectionof loops. = + 1:13If >1theremustbeanedgeewhichis nota getG eis connected. (G e) = (G) (G e) = (G) 1 (G e) = (G) 1 Butthen (G) (G) + (G) = (G e) (G e) + (G e)= 2by 1 Allplaneembeddingsofa planargraphGhave thesamenumber + 2 IfGis a simpleplanegraphwith 3then 3 6:ProofEvery facehasat least3 edges. Thus2 =Xf2Fd(f) 3 :(1)Thusby Euler s formula, +23 2:2It followsfromtheabove proofthatif = 3 6thenthereisequalityin(1)andsoevery 3 IfGis a planargraphthen (G) 2 6 12:2 Corollary 4 IfGis a planargraphthen (G) planarweseethatthecolouringnumber (G) 5K5is (K5) = 10>3 (K5) 6 = 9:216 Corollary 6K3;3is ;3hasnooddcyclesandsoif it couldbeembeddedin theplane, every facewouldbeof size whichcase4 Xf2Fd(f) = 2 = 18andso s formula,2 = 6 9 + 1; s TheoremAsub-divisionofa graphGis onewhichis obtainedby replacingedgesby (vertex disjoint) , ifGisplanarthenany graphis non-planariff it containsa sub-divisionofK3; planarthen (G).
4 Trivialfor = >1verticesandtheresultis vcanbeproperly5-coloured, (v) 4thenwe cancolourvwitha colournotusedby oneof (v) = 5. Take canassumethatc(vi)6=c(vj)fori6=jelsewe canextendthecolouringctovaspreviously. We canalsoassumethatc(vi) =ifor1 i v:c(u) =ifor1 i 5andletHi;j=H[Ki[Kj]for1 i < j ;3. Ifv1andv3belongtodifferentcomponentsC1; C3ofH1;3thenwe caninterchangethecolours1 and3 inC1togeta new propercolour-ingc0ofHwithc0(v1) =c0(v3) = pathP1;3fromv1tov3whichonlyusesverticesf romK1[ insidethecycle(v1; v; v3; P1;3; v1),21vvvvvv12345P1,3 Now considerH2;4. We claimthatv2andv4areindifferentcomponents C2; C4, inwhichcasewe caninterchangethecolours2 and4 inC2togeta newcolouringc00withc00(v2) =c00(v4).Ifv2andv4arein thesamecomponentofH2;4thenthereisa pathP2;4fromv2tov4whichonlyusesverticeso fcolour2 tocrossP1;3whichonlyusesverticesofcolour 1 and3]]
