Grafos planares e triangulación de superficies

Traballo Fin de Grao Grafos planares e triangulación de superficies Noel Rodil López Xullo, 2022 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA GRAO DE MATEMÁTICAS Traballo Fin de Grao Grafos planares e triangulación de superficies Noel Rodil López Xullo, 2022 UNIVERSIDADE DE SANTIAGO DE COMPOSTELA Traballo proposto Área de Coñecemento: Xeometría e Topoloxía Título: Grafos planares e triangulación de superficies Breve descrición do contido Un teorema de Kuratowski establece que un grafo é planar (mergullable no plano) se e só se non contén o grafo completo con 5 vértices nen o grafo bipartito de 3+3 vértices. Seguindo un famoso artigo de Carsten Thomassen, expoñerase unha demostración sinxela dunha parte deste teorema, que logo se usará para dar unha demostración sinxela do teorema de Jordan-Schonflies, e como consecuencia obter que toda superficie é triangulable. Recomendacións Especialmente interesante para alumnos que lles gustara a materia “Topoloxía de superficies”. Outras observacións iii Índice Resumo vii Introdución ix 1. Grafos Planares e Teorema da Curva de Jordan 1 2. Teorema de Jordan-Schönflies 13 3. Triangulación de superficies pechadas 19 4. Clasificación de superficies pechadas 25 A. Anexo I: Un contraexemplo ó teorema de Jordan-Schönflies en dimensión 3 35 B. Anexo II: O xénero dun grafo e a coloración de mapas 41 v Resumo Neste traballo, levaremos a cabo un estudo detallado dun artigo publicado por Carsten Thomassen en 1992, no que presenta probas elementais de catro grandes teoremas, culminando co Teorema de Clasificación de Superficies Pechadas. Profundizaremos nos resultados e as probas expostas neste artigo, e propoñeremos algún resultado adicional para facelo máis doado de seguir. Tamén engadiremos numerosas ilustracións dos conceptos e probas máis importantes, e aclararemos todos os detalles que o autor deixa ao lector. Todo isto, co fin de facilitar a comprensión das ideas expostas polo autor. Por último, presentaremos un contraexemplo a unha xeralización dun dos principais resultados do artigo, o Teorema de Jordan-Schönflies, xunto cunha aplicación do Teorema de Clasificación de Superficies Pechadas ao problema da coloración de mapas. Abstract In this work, we will carry out a detailed study of an article published by Carsten Thomassen in 1992, in which he presents elementary proofs of four important results, ending with the Classification Theorem for Closed Surfaces. In order to facilitate the understanding of the article, we will delve in the results and proofs contained in the article, and propose some other results from outside the article in order to make it easier to follow. We will also ilustrate the most important concepts and proofs, and clarify the many details the author has left for the reader. Finally, we present a counterexample to a generalisation of one of the main results of the article, the Jordan-Schönflies Theorem, as well as an application of the Classification Theorem for Closed Surfaces to the map coloring problem. vii 4 1. Grafos Planares e Teorema da Curva de Jordan Demostración. Sexa Γunha representación de Gno plano. Para cada vértice p∈Γ, tomamos un disco pechado Dpde forma que só interseque ás arestas que inciden en pe a a unión de todos os discos sexa disxunta. Agora, para cada aresta pq de Γ, tomamos o arco pq =pq ∩(R2/(˚ Dp∪˚ Dq)) e engadímoslle un segmento en cada un dos dous discos conectando peqcos extremos de pq. Como R2é Hausdorff, e os arcos pq, p, q ∈Γson compactos disxuntos, existen abertos disxuntos que conteñen a cada un dos arcos, e polo tanto podemos aplicar o Lema 1.5 para sustituilos por arcos simples en cada aberto. Figura 1.3: Lema 1.14 Lema 1.15. Se Cé unha curva simple poligonal pechada en R2,R2/C posúe dúas rexións con Ccomo fronteira. Demostración. Probando que R2/C ten como moito dúas rexións e que non é arconexo, obtemos o resultado. Vexamos que ten como moito dúas rexións. Supoñamos que q1, q2, q3pertencen a 3 rexións distintas de R2\C. Sexa Dun disco tal que D∩Cé un segmento de recta. Agora, podemos levar cada un dos 3 puntos cara o disco a través dun arco simple poligonal sen intersecar C. Non habería máis que desplazarse paralelamente ós segmentos de Ca unha distancia pequena. Polo tanto, dous dos tres puntos están conectados a traves dun arco simple poligonal. Vexamos agora que R2\Cnon é arconexo. Sexa q∈R2\C. Tomemos unha semirrecta L dende qcon dirección arbitraria. L∩Cé unha unión finita de intervalos (posiblemente, puntos). Dado Q, un destes intervalos, se Cpasa dun lado ao outro de Lao percorrer Q, diremos que Ccorta a Len Q. No caso contrario, diremos que Ctoca a Len Q. Ao cambiar a dirección de L, o número de veces que Ccorta a Lmódulo 2 non varía. Isto ocorre xa que cando nos atopamos cun novo vértice, ou Ccorta a Lnese vértice, co que o número de cortes non varía ou ben Ctoca a L, co que o número de cortes ao cambiar de dirección aumenta ou disminúe en 2. 5 Polo exposto anteriormente, a paridade mantense fixa para calquer punto dentro do mesmo arco poligonal en R2/C (non hai máis que mudar a dirección de Lna dirección que se está a percorrer no arco). Por tanto, a paridade é a mesma para todos os puntos dunha rexión de R2/C. Agora ben, considerando unha semirrecta dende Qque interseque a Cprecisamente unha vez, obtemos puntos de distinta paridade, e polo tanto, en diferentes rexións. Figura 1.4: Lema 1.15: Teorema da curva de Jordan para curvas poligonais A rexión non acotada de R2/C chamarase exterior de C, e a rexión acotada será o interior de C. Denotaremolos como ext(C)eint(C)respectivamente. Ademáis definimos ext(C) = C∪ ext(C)eint(C) = C∪int(C). Este último resultado é un caso particular do teorema da curva de Jordan para curvas pechadas simples poligonais. Unha das probas clásicas, apoiase neste lema, xunto con outros resultados de aproximación de curvas simples arbitrarias mediante curvas poligonais, para probar o teorema da curva de Jordan (véxase [Tve93]). Sen embargo, neste caso, o autor emprega este resultado para probar de forma moi sinxela a non planaridade de K3,3, o que máis adiante será de vital importancia para a proba que pretendemos construir. O seguinte lema é unha extensión do lema anterior. Lema 1.16. Sexa Cunha curva simple poligonal pechada e Pun arco simple en int(C)tal que Pconecta p, q ∈C, e P∩P={p, q}. Sexan P1, P2∈Cos dous arcos de paq. Logo, R2/(C∪P) posúe precisamente 3 rexións, con fronteiras C,P1∪P, e P2∪Prespectivamente. Demostración. Primeiramente, ext(C)é unha das rexións de R2/(C∪P). Agora, procedemos igual que no lema anterior, tomando un disco Dtal que D∩Pé un segmento de recta, e concluimos que int(C)ten ao sumo dúas rexións. Agora temos que ver que ten polo menos dúas rexións. 6 1. Grafos Planares e Teorema da Curva de Jordan Sexan L1eL2dous segmentos de recta cruzados de forma que L1⊂PeL1∩L2={p} ⊂ P. Pola proba do lema anterior, vemos que os extremos de L2están en en dúas rexións distintas de R\(P∪P1), e polo tanto en dúas rexións distintas de R\(P∪C). Como tamén estan en int(C), concluimos que int(C)ten polo menos dúas rexións distintas. Figura 1.5: Lema 1.16 Observación 1.17.O anterior lema implica que dados dous puntos r, s en P1eP2respectivamente, ambos distintos de peq, non é posible unir rescun arco simple poligonal en int(C)sen intersecar aP. Lema 1.18. K3,3non é planar. Demostración. Podemos representar K3,3coma un ciclo C:x1x2x3x4x5x6con tres cordas x1x4, x2x5, x3x6. Se K3,3fose planar, poderíamolo representar de dita forma con Cunha curva simple poligonal pechada. Agora, tendo en conta a observación 1.18, como dous das cordas deben atoparse en int(C)ou ext(C), chegamos a unha contradicción. De forma idéntica, tamén poderíamos probar que K5tampouco é planar. Isto constitue unha das partes do teorema de Kuratowski1. 1Un grafo é planar se e só se non conten a ningunha subdivisión dos grafos K5ou K3,3. 7 Figura 1.6: Lema 1.18. Non se pode conectar x3con x6no interior nin no exterior Proposición 1.19. Se C é unha curva pechada simple en R2, entón R2/C non é conexo. Demostración. Definamos L1(resp. L2) como as rectas verticales que deixan Cna metade do plano pechado partido por L1(resp. L2). Sexa p1(resp. p2) o punto superior de L1∩C(resp. L2∩C), e P1eP2as curvas en Cde p1ap2. Sexa L3outra recta vertical entre L1eL2. Como P1∩L3eP2∩L3son compactos disxuntos, existe L4⊂L3un intervalo conectando P1eP2tal que L4∩C={p5, p6}con p5ep6en P1eP2respectivamente. Sexa L5un arco poligonal en ext(C)formado por dous segmentos de L1eL2unidos mediante un segmento por enriba de C. Se L4estivese en ext(C), existiria un arco simple poligonal L6conectando puntos medios p3ep4 de L4eL5respectivamente. Observemos que p1conéctase a p4,p5ep6a través de L4,P1eP2 respectivamente, e o mesmo ocorre para p2ep3(con diferentes arcos). Logo, C∪L4∪L5∪L6 sería un grafo planar isomorfo a K3,3, contradecindo ao lema anterior. Polo tanto, o punto medio de L4non está en ext(c), polo que está en int(C). Para demostrar o teorema da curva de Jordan, só nos queda entón probar que R2\Cnon ten máis de dúas rexións. 8 1. Grafos Planares e Teorema da Curva de Jordan Figura 1.7: Proposición 1.21 Lema 1.20. Se Gé un grafo 2-conexo e Hun subgrafo 2-conexo de G, entón podemos construir Ga partir de Hengadindo sucesivamente camiños de forma que cada un destes camiños teña por vértices inicial e final dous vértices distintos do grafo actual, é o resto dos vértices estén fora do grafo actual. Demostración. A proba será por inducción no número de aristas de E(G)\E(H). Se este número e cero, teríamos G=H, polo que asumimos que é distinto de 0. Pola hipótese de inducción, temos que o resultado cúmprese para dous grafos G′, H′tales que |E(G′)\E(H′)|<|E(G)\E(H)|. Sexa H′un subgrafo propio 2-conexo maximal de Gcontendo a H. Se Hfose un subgrafo propio de H′, poderíamos aplicar a hipótese de inducción dúas veces, primeiro sobre H′eH, e posteriormente sobre GeH. Polo tanto, podemos asumir que H=H′. Como Gé conexo, existe unha arista x1x2en E(G)\E(H)de forma que x1∈H. Se x2∈H,H∪x1x2=Gpola maximalidade de H. Logo, supoñamos que x2non está en H. Xa que G−x1é conexo (Gé 2-conexo), existe un camiño x2x3...xkde forma que xk∈Hexi/∈H: 2 ≤i<k. Agora ben, dado que H∪P∪x1x2 é 2-conexo, e de novo pola maximalidade de Hobtemos que H∪P∪x1x2=G. Lema 1.21. Se Γé un grafo planar 2-conexo de polo menos 3 vértices, cuxas aristas son arcos simples poligonales, logo R2\Γten |E(Γ)|−|V(Γ)|+ 2 rexións, cada unha delas cun ciclo de Γ como fronteira. Demostración. Sexa Cun ciclo de Γ. Polo lema 2.3, o resultado quedaría probado se Γ = C. Noutro caso, podemos obter Γa partir de Cengadindo camiños sucesivamente do xeito explicitado no lema anterior. Cada un destes camiños é engadido dentro dunha rexión, que está acotada 9 por un ciclo, e polo tanto, podemos aplicar o lema 2.4, concluindo que por cada camiño engadido, subdividindo unha rexión, aumentamos o número de rexións en 1, o que remata a proba, se observamos que ao engadir un camiño cos extremos no grafo actual e os demais vértices fora del, estamos engadindo nvértices e n+ 1 arestas. Se Γé un grafo plano, chamaremos caras de Γás rexións de R2\Γ. Ademáis, se Γé 2-conexo, a rexión non limitada será a cara exterior de Γ, cuxa fronteira será o ciclo exterior de Γ. Definición 1.22. Se GeHson dous grafos, definimos a unión G∪H= (V(G)⊔V(H), E(G)∪E(H)) . Para os grafos planos, convén definir a unión de distinta forma, co fin de conservar a planaridade. Definición 1.23. Sexan Γ1eΓ2dous grafos planos con arcos simples poligonales como arestas. A súa unión Γ1∪Γ2construirase da seguinte forma: Sexa Γ′ iunha subdivisión de Γide forma que cada aresta sexa un segmento de recta para i= 1,2. Agora, sexa Γ′′ iunha subdivisión de Γ′ ide maneira que un punto pdunha aresta ade Γ′ i sexa vértice de Γ′′ ise pé un vértice de Γ′ 3−iou ben pestá nunha aresta de Γ′ 3−iintersecando a a. Por último, a unión usual definida anteriormente entre Γ′′ 1eΓ′′ 2é un grafo plano que tomará o papel de Γ1⊔Γ2. Figura 1.8: Unión de grafos planares 10 1. Grafos Planares e Teorema da Curva de Jordan Lema 1.24. Sexan Γ1,Γ2, ...Γkgrafos planos 2-conexos cuxas arestas son arcos simples poligonales de forma que cada Γi(i= 2,3..., k −1) ten polo menos dous puntos en común con Γi−1e con Γi+1, e ningún punto en comun co resto dos Γj. Supoñemos ademais que Γ1∩Γk=∅. Entón, todo punto que se atope na cara exterior de cada Γi∪Γi+1 (i= 1,2, ..., k −1) está tamén na cara exterior de Γ1∪Γ2∪... ∪Γk. Demostración. Supoñamos que pé un punto nunha cara interior de Γ1∪... ∪Γk. Dado que Γ1∪... ∪Γké 2-conexo, séguese do lema 1.21 que existe un ciclo Cen Γ1∪... ∪Γktal que p∈int(C). Podemos escoller Cde forma que Cesté en Γi∪Γi+1... ∪Γjej−isexa mínimo. Vexamos que j−i≤1. Supoñamos entón que j−i≥2. De novo, podemos asumir que o número de arestas de Cque non están en Γj−1é mínimo. Como Cinterseca a Γj−2e a Γj,Cten polo menos dous segmentos disxuntos maximales en Γj. Sexa Pun deles, e P′o camiño máis curto en Γj−1entre PeC−V(P). Os extremos de P′dividen Cen dous arcos, P1eP2, e cada un deles conten segmentos fora de Γj−1. Necesariamente, un dos dous ciclos, P∪P1ou P∪P2contena pno seu interior, e ten menos segmentos fora de Γj−1dos que ten C, o que contradice a minimalidade na elección de Casumida anteriormente, polo que se Cé escollido desa forma, Cnon pode estar na unión minimal Γi∪Γi+1... ∪Γjcon j−i≥2. Teorema 1.25 (do arco).Se Pé un arco simple en R2,R2\Pé arconexo. Demostración. Sexan peqdous puntos en R2\P, e sexa d∈Rtal que peqestean a distancia >3dde P. Dado que Pé a imaxe dunha aplicación continua (uniformemente xa que o dominio é compacto), podemos dividir Pen segmentos P1, P2...Pkde forma que Pivai de piapi+1 e tal que a distancia de cada punto de Piapisexa menor que d, para i= 1,2, ..., k −1. Sexa d′a minima distancia entre PiePi+1, i ∈ {1,2, ..., k −1}. Dividiremos agora cada P1en segmentos Pi,j de forma que Pi,j vai de pi,j api,j+1 e a distancia entre cada punto de Pi,j api,j é menor que d′/4. Sexa Γio grafo formado pola unión das fronteiras dos cadrados de centro pi,j e lado d′/2. Observamos que os Γisatisfacen as condións do lema anterior. Observemos agora que dado que Γi∪Γi+1 está contido no disco de radio 3dcentrado en pi+1, mentras que peqnon, e aplicando o lema anterior, temos que peqestán na cara exterior de Γ1∪Γ2∪... ∪Γk. Ao mesmo tempo, Pnon interseca a esta cara, polo que podemos unir peqmediante un arco simple poligonal disxunto de P. Observación 1.26.Se Cé un subconxunto pechado do plano e Ωé unha rexión de R2\C, diremos que un punto p∈Céaccesible dende Ωse para algún punto qde Ω(e polo tanto todos), existe un arco simple poligonal entre peq, intersecando a C soamente en p. É unha curiosa observación que se Cé unha curva simple pechada e p∈C,pnon é necesariamente accesible, dado que como dixemos na introdución, existen curvas con comportamentos patolóxicos, con puntos aos que non é posible acceder mediante un arco simple poligonal, xa que este está formado por un número 11 finito de segmentos. Por outra parte, se Pé un segmento de Cque contén a p, polo teorema anterior, R2\(C\P)é arconexo, e polo tanto existe un arco simple poligonal P′dende qata outro punto contido nunha rexión de R2\Cdiferente de Ω, e logo P′interseca a Cnun punto de P. Dado que podemos escoller un Parbitrariamente pequeno, deducimos que o conxunto de puntos accesibles de Cé denso en C. Teorema 1.27 (da curva de Jordan).Se Cé unha curva simple pechada en R2,R2\Cten exactamente dúas rexións, cada unha delas con Ccomo fronteira. Demostración. Supoñamos que existen 3 puntos q1, q2, q3tales que se atopan cada un deles nunha rexión diferente de R2\C. Sexan Q1, Q2, Q3segmentos de Cdisxuntos dous a dous. Aplicando a observación anterior, temos que existe un arco simple poligonal Pi,j de qiaQjcon i, j = 1,2,3. Podemos asumir que Pi,j ∩Pi, j′=qise j=j′, xa que se por exemplo ao percorrer Pi,2cara qinos atopásemos con Pi,1no punto q′ i, poderíamos modificar Pi,2de forma que o seu último segmento este moi preto do segmento de Pi,1que vai de q′ iaqi, sen tocalo, e o único punto en común con Pi,1sexa qi. Como os qise atopan en rexións distintas, Pi,j ∩Pi′,j =∅se i=i′. Agora, considerando como vértices a os qi, podemos extender a unión dos arcos Pi,j, engadindo para cada Qiun vértice no punto intermedio dos tres nos que cada arco Pi,j interseca a Qi, e completando as arestas cos segmentos de Qique une estes puntos intermedios aos outros dous, de forma que obtemos unha representación plana de K3,3, o cal sabemos que non pode ocorrer, polo que R2\Cten menos de 3 rexións, e polo visto na proposición 1.19, concluimos que R2\C ten exactamente dúas rexións, int(C)eext(C). Ademáis, o teorema do arco tamén implica que todo punto de Cé un punto fronteira de int(C)eext(C). Figura 1.9: Proposición 1.21 12 1. Grafos Planares e Teorema da Curva de Jordan Observación 1.28.É moi fácil ver que un grafo é mergullable no plano se e só se é mergullable na esfera. É obvio que calquer grafo planar é mergullable na esfera, e para ver que o recíproco é certo, só habería que eliminar un punto da esfera que non pertenza ó grafo, co cal obteríamos un espazo homeomorfo a R2. Por isto último, tamén é certo o teorema do arco para unha esfera. Polo tanto, o teorema da curva de Jordan é válido para curvas pechadas simples en esferas. Capítulo 2 Teorema de Jordan-Schönflies Agora imos a probar o resultado central deste traballo, que forma unha ponte entre o teorema da curva de Jordan (do que é unha xeralización) e o teorema de triangulación de superficies pechadas. Xa temos case todo o necesario, soamente nos fará falta extender un par de resultados do capítulo anterior. Comezamos cunha extensión do lema 1.17. Lema 2.1. Sexa Cunha curva simple pechada e Pun arco simple poligonal en int(C)unindo os puntos peqe con ningún outro punto en común con C. Sexan P1eP2os dous arcos en Cde paq. Entón, R2\(C∪P)ten exactamente 3 rexións con fronteiras C,P1∪PeP2∪P respectivamente. Demostración. Ao igual que na proba do lema 1.17, só nos falta probar que int(C)se divide en polo menos dúas rexions. Sexan L1eL2dous segmentos cruzados de forma que L1⊂Pe L1∩L2={p} ⊂ P. Se os extremos de L2estivesen na mesma rexión de int(C), existiría un arco simple poligonal P3tal que L2∪P3é unha curva simple poligonal pechada. Pola proba do lema 1.15, os extremos de L1están en distintas rexións de R2\(L2∪P3). Ao mesmo tempo, os extremos de L1están na mesma rexión de R2\(L2∪P3), dado que están conectados por un arco simple en P∪Cque non interseca a L2∪P3. Esta contradicción implica que os extremos de L2 están en distintas rexións de int(C), o que remata a proba. Tamén obtemos a seguinte xeralización do lema 1.23. Lema 2.2. Se Γé un grafo plano 2-conexo que contén a un ciclo C, sendo Cunha curva simple pechada, de forma que todas as arestas de Γ\Csexan arcos simples poligonales en int(C), entón R\Γten |E(Γ)|−|V(Γ)|+ 2 rexións, cada unha delas cun ciclo de Γcomo fronteira. Demostración. A proba é idéntica á do lema 1.23, pero empregando o lema anterior en lugar do lema 1.17. 13 20 3. Triangulación de superficies pechadas Figura 3.1: Unha superficie pechada, o tetrahedro Observación 3.4.Gpode conter arestas múltiples e lazos, polo que non necesariamente é un grafo. Aínda así, a partir de calquer mergullo 2-celular Gé posible obter unha triangulación, procedendo da seguinte forma. Se Gnon é grafo, subdividimos as arestas paralelas e os lazos que poida haber, de forma que obtemos un grafo. Agora, despois de facer as correspondentes divisións nos lados dos póligonos se fose necesario, cada cara de Gque sexa un polígono convexo con máis de 3 lados é sinxela de triangular. Imos a describir un procedemento xeral, aínda que podería facerse de calquer xeito. Sexan v1, v2, ..., vrcon r≥4os vértices do polígono, con índices expresados módulo r. Engadimos r+1 novos vértices u, u1, ..., urno interior do polígono, xunto coas arestas uivi, uivi+1, uiui+1, uiu. Unha vez separados, os triángulos obtidos inducen un novo grafo G′. Cabe observar que E(G) = E(G′). Na seguinte figura ilustramos os anteriores procedementos cun exemplo no que Sé o toro (definiremos esta superficie no seguinte capítulo). Cabe observar que este método de triangulación de polígonos está construido de forma que o resultado non conteña lazos nin arestas múltiples, polo que o resultado final de todo o procedemento sempre é unha triangulación. . 21 Figura 3.2: Triangulación do toro Probamos agora un resultado auxiliar para a demostración do seguinte teorema. Lema 3.5. ([Jea13],Lema E.2) Sexan C, C2, C3⊂R2tres curvas pechadas simples, tal que C3⊂int(C2). Definimos un "mal segmento"de Ccoma un segmento P⊂Cde forma que P⊂int(C2)eP∩C2={p, q}. Definimos tamén un "moi mal segmento"coma un mal segmento que interseca a C3. Logo, nas condicións anteriores, só existe un número finito de segmentos moi malos. Demostración. Observemos que como as curvas son conxuntos compactos (imaxe por aplicación continua de [0,1]), e C3⊂int(C2), existe un ϵ > 0para o que C3ten un recubrimento finito formado por discos de radio ϵ, todos eles contidos en int(C2). Supoñamos que existen infinitos segmentos moi malos, e sexa {Pn}unha sucesión de ditos segmentos. Cada un destes segmentos correspóndese cos dous puntos nos que interseca a C2,pn 22 3. Triangulación de superficies pechadas eqn. Se C=γ([0,1]), temos que pn=γ(un)eqn=γ(vn), polo que podemos formar a sucesión {tk}, definida por t2k−1=uket2k=vk. Como [0,1] é compacto, esta sucesión ten un punto de acumulación t. Ademáis, dado que as curvas son compactas, ambas as dúas sucesións {pn}e {qn}teñen algunha subsucesión converxente a γ(t) = s, do que deducimos que sestá en C2e por tanto en C∩C2. Como C=γ([0,1]) é unha curva continua, dado η > 0,∃ϵ2>0tal que |u−t|< ϵ2=⇒γ(u)∈B(s, η). Dado que té un punto de acumulación de {tk}, isto implica que existe algún ukou vka distancia < ϵ2de t, polo que hai algún moi mal segmento Pn⊂B(s, η). Agora ben, se escollemos η < ϵ, pola observación inicial, dito segmento non intersecaría a C3, o cal é unha contradicción. Por tanto, só existe un número finito de segmentos moi malos. Teorema 3.6. Toda superficie pechada é homeomorfa a unha superficie triangulada. Demostración. Polo que observamos anteriormente, só será necesario probar que toda superficie pechada é homeomorfa a unha superficie cun mergullo 2-celular. Para cada punto p∈S, sexa D(p)un disco aberto do plano homeomorfo a un entorno aberto Upde pa través dun homeomorfismo θp:D(p)→Up. Consideramos en D(p)dous cuadriláteros Q1(p)eQ2(p)tales que Q1(p)⊂int(Q2(p)) e con p∈θp(int(Q1(p))). Como Sé compacto, existe un número finito de puntos p1, p2, ..., pnde forma que S=Sn i=1 θi(int(Q1(pi))). Como os discos D(pi)son subconxuntos do plano, podemos asumir que son disxuntos dous a dous. O problema fundamental que se nos presenta, é que é posible que os θi(Q1(pi)) iniciais se intersequen de formas moi complicadas (están formados por arcos simples non necesariamente poligonais), podendo chegar a intersecarse infinitas veces, o que imposibilitaría a construcción dun mergullo 2-celular e por iso, no que ven, manteremos os D(pi)fixos no plano, pero modificaremos os homeomorfismos θPi, e en consecuencia os conxuntos correspondentes UPi=θpi(D(pi)), considerando despois novos cuadriláteros Q1(pi)que formen un mergullo 2-celular de S. Procedendo por inducción, supoñamos que Q1(p1), ..., Q1(pk−1)foron elixidos de forma que calesquera dous cuadriláteros de θp1(Q1(p1)), ..., θpk−1(Q1(pk−1)) teñan intersección finita en S. Agora vexamos o que ocorre en Q2(pk). Definimos un “mal segmento” coma un segmento Pde algún Q1(pj),(1 ≤j≤k−1) de forma que θpj(P)conecta dous puntos de θpk(Q2(pk)) e ten o resto dos puntos en θpk(int(Q2(pk))). Cada mal segmento ten unha imaxe en Q2(pk), dada por θ−1 pk(θpj(P)), á que chamamos “mal segmento” en Q2(pk). Sexa Q3(pk)outro cuadrilátero tal que Q1(pk)⊂int(Q3(pk)) eQ3(pk)⊂int(Q2(pk)). Decimos que un mal segmento Pé un “moi mal segment” se θpj(P)interseca a θpk(Q3(pk)). É posible que existan infinitos malos segmentos, xa que podería existir un segmento dalgún Q1(pj) que se “revolvese” infinitas veces intersercando a Q2(pk)infinitas veces. En cambio, como estamos nas condicións do lema anterior (Q3(pk)⊂int(Q2(pk)), sabemos que só existe un número finito de segmentos moi malos. 23 Os segmentos moi malos θ−1 pk(θpj(P)) dentro de Q2(pk)xunto con Q2(pk)forman un grafo plano 2-conexo Γ. Polo lema 1.20, sabemos que podemos redebuxar Γdentro de Q2(pk)de forma que obtemos un grafo Γ′plano-isomorfo (e por tanto homeomorfo) a Γno que todas as arestas sexan arcos simples poligonais. Agora, aplicando o corolario 2.5, extendemos o planoisomorfismo a un homeomorfismo de int(Q2(pk)deixando fixo Q2(pk). Este homeomorfismo transforma Q1(pk)eQ3(pk)en curvas simples pechadas Q′ 1eQ′ 3en int(Q2(pk)) tal que Q′ 1⊂Q′ 3 epk∈θpk(int(Q′ 1)). Vexamos que existe unha curva simple poligonal Q′′ 3⊂int(Q2(pk)), de forma que Q′ 1⊂ int(Q′′ 3)e non interseque a ningún mal segmento que non sexa moi malo. Efectivamente, se para cada p∈Q′ 3escollemos un cadrado R(p)de centro pque non interseque nin a Q1nin a ningún mal segmento que non sexa moi malo. Estes cadrados recubren Q′ 3. Logo, tomando un subrecubrimento finito (Q′ 3é compacto), a unión destes cadrados forma un grafo plano 2-conexo, cuxo ciclo exterior pode tomar o papel de Q′′ 3. Se fose necesario, podemos xirar algún dos cadrados en torno ó centro para que a intersección cos segmentos moi malos sexa finita (podémolo facer, dado que os segmentos moi malos son arcos simples poligonais, formados por un número finito de segmentos de recta, polo que só existe un número finito de direccións). Agora, ao igual que fixemos antes, podemos redibuxar Γ′∪Q′′ 3, que é un grafo plano 2- conexo, de forma que Q′′ 3sexa un cuadrilátero (que contén a Q′ 1no seu interior), e extender o plano-isomorfismo de grafos a un homeomorfismo de int(Q2(pk)) grazas ó corolario 2.5. Dado que Q′ 1⊂int(Q′′ 3), podemos escoller a Q′′ 3como o novo Q1(pk), e seguirase cumprindo S=Sn i=1 θi(int(Q1(pi))), ademáis de que θpk(Q1(pk)) terá intersección finita con cada un dos θpi(Q1(pi)) (1≤i≤k−1). A hipótese de inducción queda así probada para todo k. Dado que S=Sn i=1 θi(int(Q1(pi))) e que a intersección entre cada dous dos θpiQ1(pi)é finita, podemos pensar en Sn i=1 θpi(Q1(pi)) coma un grafo Γmergullado en S. Cada rexión de S\Γestá limitada por un ciclo C. Agora, para cada Cdebuxamos un polígono convexo C′de lado 1de forma que os vértices de C′se correspondan cos vértices de C, e obtemos a superficie S′identificando os lados de todos os polígonos adecuadamente para que o grafo inducido do 2-mergullo celular Γ′en S′sexa isomorfo a Γ. Podemos extender facilmente o isomorfismo entre ΓeΓ′(pensando en ΓeΓ′como grafos abstractos) a un homeomorfismo f: Γ ⊂S→Γ′⊂S′. En particular, a restricción de faCé un homeomorfismo de Cen C′. Claramente, para algún i,Cestá contido en θpi(int(Q2(pi))), homeomorfo a R2, mentres que int(C′)é o interior dun polígono convexo, polo que podemos aplicar o teorema de Jordan-Schönflies para extender f|C aint(C). Procedendo deste xeito para todas as rexións de S\Γ, obtemos un homeomorfismo entre SeS′. 24 3. Triangulación de superficies pechadas Figura 3.3: Teorema 3.5 Capítulo 4 Clasificación de superficies pechadas Xa probado que toda superficie pechada é homeomorfa a unha superficie triangulada, imos a describir un conxunto de superficies pechadas e probaremos que toda superficie pechada é homeomorfa a unha delas. Para rematar, veremos que ningunha das superficies descritas é homeomorfa a outra. Como consecuencia, teremos probado o teorema de clasificación de superficies pechadas. Definición 4.1. Sexa Funha cara dunha superficie Scon un 2-mergullo celular. Dentro dela, consideremos dous triángulos disxuntos T1eT2. Eliminamos os interiores dos triángulos, e formamos unha superficie S′identificando os lados dos triángulos de forma que as orientacións no plano dos lados coincida. Formamos outra superficie S′′ identificando os lados de forma que as orientacións no plano sexan opostas. Decimos que S′eS′′ son obtidas a partir de Sengadindo un asa torcida ou un asa respectivamente. Se en lugar de dous triángulos consideramos un cadrado, borramos o seu interior, e indentificamos os puntos "diametralmente opostos", como se mostra na figura, obtemos unha superficie S′′′, a cal diremos que é obtida a partir de Sengadindo unha tapa cruzada (realmente estamos a pegar unha banda de Möbius polo seu borde). É claro que non ten importancia a localización dos triángulos ou cuadrilateros dentro da mesma cara, nin tampouco a elección da cara Fna que os situamos. Tamén é posible que os dous triángulos se atopen en diferentes caras, aínda que por agora non seríamos capaces de distinguir entre os dous tipos de asa. Ademais, ao engadir unha tapa cruzada, non é necesario empregar un cuadrilátero, se non que identificando puntos opostos en calquera curva simple pechada, obteríamos a mesma superficie (salvo homeomorfismo) Tamén podemos representar as asas e as asas torcidas considerando un cuadrilátero é identificando os lados debidamente, da forma indicada nas seguintes figuras. E fácil ver que estas representacións son equivalentes. Procedendo dun xeito similar, podemos probar graficamente o seguinte lema. 25 26 4. Clasificación de superficies pechadas Figura 4.1: Asa, asa torcida e tapa cruzada Lema 4.2. A adición dun asa torcida é equivalente a engadir dúas tapas cruzadas. Ademáis, unha vez que temos engadido unha tapa cruzada, a adición dun asa é equivalente á dun asa torcida. Demostración. A proba está ilustrada a continuación. Só resta ver que os cuadrilateros da primeira e última ilustración da segunda parte do lema son, respectivamente, equivalentes ós triángulos que forman unha asa ou unha asa torcida, o cal é moi sinxelo de ver empregando o mesmo método da demostración. Figura 4.2: Asa torcida =2 tapas cruzadas 27 Figura 4.3: Asa +tapa cruzada =asa torcida +tapa cruzada Agora, consideremos todas as superficies obtidas do xeito anterior, a partir da esfera S0, pensada coma un cociente de polígonos (tetrahedro). Engadindo hasas á esfera, obtemos unha superficie que denotaremos por Sh, e chamaremos superficie orientable de xénero h. Se en cambio engadimos ktapas cruzadas, obtemos outra superficie, á cal denotaremos por Nk, e chamaremos superficie non orientable de xénero k. Máis adiante, veremos o porqué desta denominación. S1, N1eN2son o toro, o plano proxectivo é a garrafa de klein respectivamente. A partir do lema anterior, dedúcese o seguinte resultado. Proposición 4.3. Sexa Sa superficie obtida a partir da esfera, engadindo hasas, tasas torcidas ectapas cruzadas. Entón, se t=c= 0,S=Sh, e noutro caso, S=N2h+2t+c. Agora probaremos o resultado fundamental deste capítulo, que nos deixará a un paso de establecer o teorema de clasificación de superficies pechadas. Imos a ver que dada unha superficie pechada S, sempre é posible transformala en S0, mediante un número finito de cortes e identificacións. En [Ots] pódese consultar unha exposición moi intuitiva e cunha visualización moi clara dunha demostración do teorema de clasificación, ideada por E.C. Zeeman, onde este 28 4. Clasificación de superficies pechadas proceso recibe o nome de “cirurxía”. Lema 4.4. Sexa Sunha superficie pechada, e Gun multigrafo mergullado en S(mediante un mergullo 2-celular), con nvértices, qarestas e fcaras. Entón Sé homeomorfo a Shou Nk, onde hekveñen dados polas ecuacións E(G) = n−q+f= 2 −2h= 2 −k(4.1) Demostración. Como Sé conexo, Gtamén. Vexamos en primeiro lugar que E(G)≤2. Para velo, eliminamos sucesivamente arestas de Gata que obtemos un subgrafo conexo minimal Hde G. En cada eliminación, o número de caras (agora non necesariamente polígonos) mantense ou redúcese en 1. É claro que Hten nvértices, n−1arestas e unha sola cara. Disto deducimos que, efectivamente, E(G)≤2. Agora, como xa vimos no capítulo anterior, podemos obter a partir do multigrafo Gun grafo G′que triangule S, e de forma que E(G) = E(G′). Polo tanto, é suficiente con probar o resultado cando Gé unha triangulación de S. Faremos unha proba por reducción ó absurdo. Supoñamos que SeGforman un contraexemplo ao lema, de forma que Gposúa polo menos 4 vértices e (1) 2−E(G)=2−n+q−fé mínimo. (2) Suxeito a (1),né mínimo. (3) A mínima valencia mde Gé mínima, suxeita a (1) e(2) (A valencia dun vértice é o número de arestas incidentes nel). Sexa vun vértice de mínima valencia en G. Sexan v1, v2, ..., vmos vértices veciños de vtal que os ciclos vv1v2, vv2v3, ...vvmv1acoten as caras adxacentes a v(cos índices expresados módulo m). Como Gé un grafo, necesariamente temos m≥3. Se m= 3,G−vé unha triangulación de S, a non ser que Ssexa o tetrahedro (entón G−vsó tería un triángulo, o cal non é unha superficie pechada). O primeiro caso contradeciría (2) e o segundo a suposición de que SeG son un contraexemplo do lema. Por tanto, temos que m≥4. Se para algún i= 1,2, ..., m, o vértice vinon está conectado a vi+2 mediante unha aresta, denotemos como G′ao grafo obtido a partir de Geliminando a aresta vvi+1 e engadindo a aresta vvi+2. É fácil ver que G′triangula a S, o que contradice (3). Entón, podemos asumir que G contén a todas as arestas vivi+2, cando vten valencia mínima. A idea do que segue de demostración é a seguinte; imos a "cortar"(eliminar as identificacións) a nosa superficie polo triángulo T=vv1v3, o cal non desconecta á superficie (Te unha curva de Spero non delimita unha cara). Ao facer esto, veremos que poden ocorrer dúas cousas; que Tse transforme en dous triángulos disxuntos, o cal ocorrería cando Tforme parte dunha asa ou asa torcida, ou que Tse transforme nun hexágono, o cal ocorre se Tforma parte dunha banda de 29 Möbius (observemos que ao cortar unha banda de Möbius polo seu meridiano non a separamos en dúas partes). Despois, “rechearemo” os ocos que quedan no interior de Tpara obter unha superficie pechada S′cun mergullo 2-celular G′, para o cal veremos que E(G′)> E(G), o que implicaría que 2−E(G′)<2−E(G), e de acordo con (1), isto implica que S′é da forma Shou Nk. Como no proceso de construcción de S′estamos a desfacer un asa, asa torcida, ou tapa cruzada, é claro que Sobtense a partir de S′engadindo unha das anteriores, polo que será da mesma forma. Imos a desenvolver agora este argumento, e para facilitar a súa visualización, apoiaremonos nun exemplo gráfico, neste caso o do toro, o cal representaría o primeiro dos dous casos aos que antes nos referiamos. É importante notar que para poder aplicar visualmente o proceso, é necesario partir dunha triangulación mínima (nas condicions anteriormente expostas). Ademáis, hai que entender a representación da figura coma un grafo, na que para aumentar a claridade e poder representar o grafo no plano (non é un grafo planar), aparecen por duplicado algúns vértices e arestas. Denotemos por Mo espacio topolóxico resultante de identficar os lados dos triágulos de S(da forma indicada pola triangulación), exceptuando os seis lados que se corresponden coas arestas vv1,v1v3ev3v, os cales deixamos sen identificar. Chamaremos a estes seis lados lados fronteira de M. Sexa G′o grafo cuxos vértices son os vértices dos triángulos de Me cuxas arestas son os lados de ditos triángulos (unha vez identificados, analogamente ó grafo que induciría Mse fose unha superficie pechada). Notemos que Gten exactamente 6 vértices incidentes con lados fronteira, e cada un destes vértices é incidente con exactamente 2 lados fronteira. Polo tanto, os lados fronteira forma un subgrafo Cformado por vértices de valencia 2. Entón, só temos dúas posibilidades para C, ou ben está formado por dous triángulos disxuntos, ou ben é un hexágono. Se Cestá formado por dous triángulos disxuntos, engadimos a Mdous novos triángulos disxuntos do plano, e identificamos os seus lados coas arestas de C, de forma que obtemos unha superficie S′triangulada por G′. Se Cé un hexágono H, engadimos un hexágono do plano (previamente triangulado) a M, e identificamos os seus lados coas arestas de C, de forma que obtemos unha superficie S′′, triangulada por un grafo G′′ (aquí é necesario extender G′dado que temos que triangular o hexagono engadido). No primeiro caso, engadimos dúas caras, polo que E(G′) = E(G)+2 (4.2) e no segundo caso, como E(H) non varía ao triangulalo, temos que E(G′′) = E(G)+1 (4.3) Por (1), temos que de ser superficies pechadas, S′ou S′′ son da forma Shou Nk, o cal é así, dado que G′é conexo pola existencia da aresta v2vm(v2está dentro de Tevmfora). Se C consiste en dous triángulos, como dixemos antes, é claro que Sobtense a partir de S′engadindo un asa, ou un asa cruzada, mentras que se Cconsiste nun hexágono, Sobtense a partir de S′′ 36 A. Anexo I: Un contraexemplo ó teorema de Jordan-Schönflies en dimensión 3 Definiremos a esfera cornuda como o límite dunha sucesión de esferas, e veremos que a pesar de ser homeomorfa á S2, o complementario da unión da esfera co seu interior non é simplemente conexo, é dicir, que existe un lazo contido nel que non se pode deformar ata un punto. Partimos da esfera S2 0a que lle engadimos unha asa, de forma que obtemos un toro, ao que chamaremos X1. Agora, removemos unha pequena sección transversal (un cilindro) da asa, obtendo así un cilindro, e tapamos con dous discos o cilindro de forma que obtemos unha esfera S2 1(análogo ó que faciamos na demostración do teorema de clasificación). A continuación, a cada un dos discos (de radio r), quitámoslle un disco menor concéntrico de radio r/2, e pegámoslle un toro pinchado (toro menos un disco) de forma que os dous toros estén "encadeados", como se mostra na figura. Desta forma obtemos o espazo X2. Agora, igual ca no paso anterior, eliminamos en cada un dos novos toros un cilindro do modo descrito na figura, e pegamos 4 tapas, de forma que obtemos unha nova esfera S2 2. Repetindo este procedemento ata o infinito, cada vegada pegando toros máis e máis pequenos a cada un dos discos resultantes de eliminar os cilindros, obtemos a esfera cornuda de Alexander A. Figura A.1: Construcción da esfera [Bin83] 37 Figura A.2: Caricatura do matemático John H. Conway coa esfera cornuda de Alexander crecéndolle na cabeza, por Simon Fraser (Guy 1983, Schroeder 1991, Albers 1994) Proposición A.4. A esfera cornuda de Alexander é unha 2-esfera. Demostración. Imos a describir un homeomorfismo hentre AeS2. ([Bin83], exercicio IV.3.A) Sexan Di, i = 0,1dous discos disxuntos en S2. Consideramos agora no interior de cada un destes discos, outros dous discos Dij, i, j = 0,1, en cada un destes 4 discos, outros 2 (8 en total) Dijk, i, j, k = 0,1, e así sucesivamente, engadindo en cada paso 2ndiscos. O homeomorfismo h levará A∩S2 2en S2\Si,j Int(Dij),A∩S2 3en S2\Si,j,k Int(Dijk), etc. Fáltanos definir hnos puntos límite, é dicir, os puntos de Aque non se atopan en ningún dos S2 i. Sexa pun destes puntos, Uta compoñente conexa de A\S2 tque contén a p, e Dto disco Dij... encerrado en h(∂Ut). Definimos h(p) = Tt∈NDt. 38 A. Anexo I: Un contraexemplo ó teorema de Jordan-Schönflies en dimensión 3 Figura A.3: Construcción de h Curiosamente, como se pode apreciar de forma clara na figura anterior, estes puntos que non se atopan en ningunha das aproximacións S2 n, chamados "puntas dos cornos", forman un conxunto de Cantor, xa que en cada paso removemos 2 discos do interior de cada novo disco, o cal é análogo á construcción do conxunto de Cantor a partir dun intervalo. Do mesmo xeito que na anterior demostración, considerando “rodaxas” da bola tridimensional en lugar de discos na esfera, poderíamos establecer un homeomorfismo entre a B, a bola cornuda (a esfera cornuda xunto co seu interior) e a bola canónica de R3, o cal quere dicir que o interior da esfera cornuda sí é homeomorfo ao interior de S2. (véxase [Bin83], exercicio IV.4.C) Vexamos agora que o exterior da bola cornuda non é simplemente conexo, seguindo unha idea de [Col07]. Sexa Lo lazo representado na figura. Daremos unha idea de porqué non se pode deformar mediante unha homotopía a un punto. Supoñamos que exista dita homotopía, Γ : S1×[0,1] → R3\B, con Γ0=LeΓ1={p}. Como S1×[0,1] é compacto, a súa imaxe por Γtamén o é. Ademáis, Γ(S1×[0,1]) é disxunto de B, que tamén é compacto, polo que a distancia entre os dous conxuntos ten que ser un número real positivo ϵ. Agora ben, na construcción da esfera cornuda descrita anteriormente, os cilindros que se sustraen dos toros en cada paso son cada vez máis pequenos, de feito poden ser tan pequenos como queramos (o radio redúcese á metade en cada paso), polo que chegado a certo paso, a distancia entre as dúas tapas dos novos cornos é menor que ϵ, facendo imposible que Γ(S1×[0,1]) pase a través dos cornos. Isto é suficiente para ver que R3\Bnon é simplemente conexo, pero pódese probar que o seu grupo fundamental é 39 un grupo libre infinitamente xerado (véxase [Hat01]). Dado que ser simplemente conexo é unha propiedade topolóxica, o exterior da esfera cornuda non é homeomorfo ao exterior de S2, e polo tanto, non podemos extender o homeomorfismo entre AeS2a un homeomorfismo de R3en R3, e concluimos que o teorema de Jordan-Schönflies non se sosten (sen restriccións) en dimensión 3. Figura A.4: [Col07] 40 A. Anexo I: Un contraexemplo ó teorema de Jordan-Schönflies en dimensión 3 Anexo B Anexo II: O xénero dun grafo e a coloración de mapas Xa sabemos que o problema dos tres servicios exposto na introdución non ten solución, tendo probado que K3,3non é planar. Tamén sabemos que podemos representar K3,3no plano cunha soa intersección entre duas arestas, o cal, se pensamos un pouco, pode dar lugar á seguinte "trampa". Se puidésemos colocar un asa no plano de forma que esta pasase por enriba da intersección, poderíamos facer pasar unha das arestas polo asa e a outra por debaixo, de forma que non se intersequen. Figura B.1: Solución ao problema dos tres servicios nunha taza Agora, como xa observamos no primeiro capítulo, un grafo é mergullable no plano se e só se 41 42 B. Anexo II: O xénero dun grafo e a coloración de mapas é mergullable nunha esfera. Xunto, co anterior, isto quere dicir que se replantexamos o problema dos 3 servicios, pensando en que as casas están no globo terráqueo (unha esfera), a solución consistiría en engadir unha asa á esfera, é dicir, transformala nun toro. Outra forma de dicir esto é que K3,3é mergullable no toro. Xa vimos que existen máis grafos non planares que sí son mergullables no toro, como por exemplo K7(a triangulación mínima do toro). Isto pode levarnos a facernos a seguinte pregunta. Dado un grafo G, existe algunha superficie orientable Shde forma que Gsexa mergullable en Sh? Claramente, a resposta é sí. Dado un grafo arbitrario, podemos representalo na esfera cun número finito de interseccións1. Logo, só temos que colocar un asa por cada unha destas interseccións e proceder do xeito descrito anteriormente. Agora ben, é necesario engadir unha asa por cada intersección para poder mergullar Gen Sh? Como dixemos antes, K7é mergullable no toro, e a súa representacion planar ten necesariamente máis dunha intersección. Polo tanto, en xeral, a resposta a esta última pregunta é non. Esta cuestión levanos a definir o xénero dun grafo. Definición B.1. Sexa Gun grafo. Definimos o xénero de G, ó que denotamos por γ(G), como o número mínimo de asas que hai que engadir a S0para poder mergullar G. É dicir, o xénero de Gé o mínimo valor de hpara o que Gpode ser mergullado en Sh. Un grafo planar ten polo tanto xénero 0, mentrás que un grafo toroidal (mergullable no toro e non planar) ten xénero 1. Como indica o autor en [Tho92], o problema de determinar o xénero dun grafo arbitrario dado é moi dificil, en particular é NP-completo. Sen embargo, para algunhas familias de grafos, sí que é posible calcular rapidamente o xénero2. Observación B.2.O xénero dun grafo está intimamente ligado ó xénero dunha superficie orientable. Se Gé un mergullo 2-celular de Sh, pola formula de Euler, temos que E(G) = n−q+f= 2−2h, polo que γ(G) = h. Esta última observación é de gran importancia, pois permítenos estudar un problema clásico, o da coloración de mapas, empregando ferramentas da teoría de grafos. Este problema consiste en saber cal é o número máximo de cores necesarias para colorear un mapa3de forma que dous paises adxacentes sempre teñan distinta cor. Agora, se lle asignamos un vértice a cada país, e representamos a adxacencia de dous paises mediante unha aresta entre os seus vértices correspondentes, obtemos un grafo G. Entón, este problema é equivalente a obter o número máximo de cores necesarias para colorear os vértices de Gde forma que dous vértices adxacentes non compartan cor. Este número é coñecido como número cromático de G, e denotarémolo por κ(G). 1O mínimo número de interseccións ao representar Gno plano é coñecido como o número de cruce de G. 2Véxase [Ano] 3Entendemos por mapa a unha subdivisión do plano ou da esfera dada por un grafo Hmergullado nela, na que asignamos a cada país unha ou máis rexións de S0\G. 43 Figura B.2: Mapa con 4 cores É fácil ver que se o territorio de cada país fose contiguo (subconxunto aberto e conexo), entón o problema reduciríase a atopar o número máximo de cores necesarias para colorear as caras dun mergullo 2-celular da esfera (ou equivalentemente, do plano). Pola observación anterior, esto é o mesmo que achar o máximo número cromático dun grafo planar ou de xénero 0. Sen embargo, se por exemplo un país tivese dous territorios non contiguos, o problema sería equivalente a atopar o número máximo de cores necesarias para colorear as caras dun mergullo 2-celular dun toro, como se pode apreciar na seguinte figura. Se permitísemos que houbese npaises que tivesen en total mterritorios non contiguos, habería que engadir ata m−nasas á esfera para poder mergullar G na superficie. Logo, o problema sería equivalente ó de atopar o máximo número cromático dun grafo de xénero ≤m−n. Figura B.3: Territorios non contiguos 44 B. Anexo II: O xénero dun grafo e a coloración de mapas O primero caso, no que os territorios son contiguos, foi o primeiro en formularse, cando Francis Guthrie, en 1852, tratando de colorear o mapa de Inglaterra, decatouse de que só eran necesarias 4 cores. Moito máis tarde, en 1976, tras varios intentos falidos por parte de notables matemáticos, foi probado por Kenneth Appel e Wolfgang Haken. É o primeiro gran teorema en ser probado por forza bruta facendo uso dunha computadora, o que se debe a necesidade de comprobar unha enorme cantidade de casos. A súa formulación en teoría de grafos é a seguinte. Teorema B.3 (das catro cores).Sexa Gun grafo planar. Entón, κ(G)≤4. Curiosamente, 9 anos antes, Gerhard Ringel e J.W.T. Youngs xa lograran probar cunha aproximación moi distinta un resultado que resolve o problema do segundo caso. Esta era a coñecida como conxectura de Heawood, e posteriormente como teorema de Ringel-Youngs, e admite a seguinte formulación. Teorema B.4 (de Ringel-Youngs).Sexa Gun grafo mergullado nunha superficie pechada S distinta de N2eS0. Entón, κ(G)≤ ⌊7+√49−24χ(S) 2⌋4. Ademais, esta é a mellor cota posible5. Para S0eN2non se cumpre a fórmula. No caso de N2o número máximo de cores necesarias é 66, e no caso de S0, ven dado polo teorema das catro cores. Corolario B.5. Sexa Gun grafo. Entón κ(G)≤ ⌊7+√1+48γ(G) 2⌋. Ademais, esta é a mellor cota posible. Por exemplo, se só houbese un país que tivese un territorio non contiguo, formado por dúas rexións, necesitariamos como máximo ⌊7+√1+48 2⌋= 7 cores para colorear o noso mapa. Notemos que o teorema de clasificación de superficies pechadas está a xogar aquí un papel fundamental, xa que del deducimos a formula de Euler, coa que estamos establecendo unha ponte entre un problema topolóxico e outro da teoría de grafos. 4Onde ⌊x⌋denota á función piso. 5Isto é o que conxeturou Heawood no seu artigo orixinal, onde xa probara a validez da cota. 6Foi probado por Philip Franklin en 1934.