UNIVERSITY OF LJUBLJANA FACULTY OF MATHEMATICS AND PHYSICS DEPARTMENT OF MATHEMATICS Andrej Vodopivec Embeddings of snarks into closed surfaces Doctoral Thesis ADVISER: Prof. Dr. Bojan Mohar Ljubljana, 2007 UNIVERZA V LJUBLJANI FAKULTETA ZA MATEMATIKO IN FIZIKO ODDELEK ZA MATEMATIKO Andrej Vodopivec Vloˇzitve snarkov v sklenjene ploskve doktorska disertacija MENTOR: prof. dr. Bojan Mohar Ljubljana, 2007 Abstract In the thesis we study embeddings of cubic graphs of class 2. Cubic graphs of class 2 with some additional connectivity requirements are called snarks. The motivationforthe study of thesegraphscomesfromattemptstoprovethefour color theorem. The four color theorem states that the vertices of every simple planargraphcanbecolored withfourcolors suchthat anytwoadjacent vertices are colored with di.erent colors. The theorem is equivalent to the statement that the edges of every simple planar 3-connected cubic graph can be colored with three colors such that every two adjacent edges are colored with di.erent colors. Theedgesof every simplecubicgraph canbecolored with eitherthree or four colors. Graphs whose edges can not be colored with three colors are said to be of class 2. The four color theorem states that 3-connected cubic graphs of class 2 are not planar. One generalization of this statement is that if acubicgraphhasapolyhedral embeddingintoanorientable surface,thenit is edge3-colorable. Thisgeneralizationisknown astheGr¨unbaum conjecture and was proposed by Gr¨unbaum in 1967. Although 40 years have passed not much progress has been made toward resolving it. Westartwiththestudy of someknownfamiliesof snarks. Wedeterminethe orientableand non-orientablegenusof .ower snarksandGoldberg snarks. We prove someresultsaboutthegenusofdotproductsofgraphsandinparticular dot products of the Petersen graph. We then study polyhedral embeddings of known families of snarks. We prove that short cycles in graphs are facial cycles in polyhedral embeddings of cubic graphs. Using this we prove that some known families of snarks do nothavepolyhedral embeddingsintoorientable surfaces. Weprovethat.ower snarksdo nothavepolyhedral embeddings(into orientable or non-orientable surfaces) and that Goldberg snarks do not have polyhedral embeddings. We construct for every non-orientable surface N a snark which has a polyhedral embedding into N. In the last section we study Kochol snarks and superposition. We prove thatKochol snarksdonothavepolyhedral embeddingsintoorientable surfaces. We de.ne the defect of a graph as a measure for how far a cubic graph is vii from having a polyhedral embedding into an orientable surface. In case the Gr¨unbaum conjecture is true we give a strong connection between the defect and the resistance of cubic graphs. (Resistance is a measure for how far a cubic graph is from having a 3-edge-coloring). We prove that the Gr¨unbaum Conjectureimpliesthat snarkswhich arefarfromhaving a3-edge-coloring are far from having a polyhedral embedding into an orientable surface. Math. Subj. Class.(2000): 05C10 Topological graph theory, imbedding, 05C15 Coloring of graphs and hypergraphs. Keywords: chromatic index, cubic graph, snark, polyhedral embedding, .ower snark, Goldberg snark, superposition, Kochol snark. Povzetek V disertaciji obravnavamo vloˇzitve kubiˇcnih grafov razreda 2. Kubiˇcni gra. razreda 2 z nekaj dodatnimi pogoji na povezanost so znani kot snarki. Moti­vacijazaˇstudij vloˇzitev snarkovprihajaizposkusovdokazaizrekaˇstirihbarv. Izrekˇstirihbarvtrdi,daje mogoˇcetoˇcke vsakega enostavenega ravninskega grafa pobarvati s ˇstirimi barvami tako, da so sosednje toˇcke pobarvane z ra­zliˇcnimabarvama. Izrekje ekvivalententrditvi,daje mogoˇcepovezave vsakega enostavnega3-povezanegakubiˇcnegagrafapovarvati stremibarvami tako,da sta dve sosednji povezavi pobarvani z razliˇcnima barvama. Povezave enos­tavnega kubiˇcnega grafa lahko pobarvamo s tremi ali pa s ˇstirimi barvami. Kubiˇcnigra.,katerihpovezavenemoremopobarvati stremibarvami, sogra. razreda 2. Izrek ˇstirih barv pravi, da 3-povezani kubiˇcni gra. razreda 2 niso ravninski. Enaizmedposploˇsitevizrekaˇstirihbarvjetrditev,da sokubiˇcni gra.,kiimajopoliedrsko vloˇzitev vkako orientabilnoploskev, razreda1. Pos­ploˇsitevje znanakotGr¨unbaumovahipotezainjebilapodanaleta1969inje po skoraj 40letihˇsevednoodprta. ˇ Studij zaˇcnemosˇstudijemznanihdruˇzin snarkov. Doloˇcimoorientabilniin neorientailni rod cvetnih snarkov in Goldbergovih snarkov. Potem ˇstudiramo rod 4-vsote grafov, posebej se posvetimo rodu 4-vsot Petersenovega grafa. Nato ˇstudiramo poliedrske vloˇzitve znanih druˇzin snarkov. Pokaˇzemo, da so kratki cikli v kubiˇcnih gra.h lica v poliedrskih vloˇzitvah. Pokaˇzemo, da cvetni snarki nimajo poliedrskih vloˇzitev niti v orientabilne niti v neori­entabilne ploskve in da Goldbergovi snarki nimajo poliedrskih vloˇzitev v ori­entabilne ploskve. Za vsako neorientabilno ploskev N konstruiramo snark, ki ima poliedrsko vloˇzitev v N. V zadnjem poglavju ˇstudiramo poliedrske vloˇzitve grafov dobljenih s su­perpozicijo. Za Kocholove snarke pokaˇzemo, da nimajo poliedrskih vloˇzitev v orientabilne ploskve. De.niramo degeneriranost grafa kot mero kako daleˇc je kubiˇcen graf od tega, da ima poliedrsko vloˇzitev. V primeru, da Gr¨unbau­mova hipoteza drˇzi, pokaˇzemo povezavo med degeneriranostjo in odpornostjo grafa. Odpornost meri,kakodaleˇcjekubiˇcengraf od tega,daima3-barvanje povezav. Pokaˇzemo,da sovprimeru,daGr¨unbaumovahipotezadrˇzi,kubiˇcni ix gra.,ki sodaleˇcod tega,daimajo3-barvanjepovezav,tudidaleˇcod tega,da imajo poliedrske vloˇzitve. Math. Subj. Class.(2000): 05C10 Topoloˇska teorija grafov, vloˇzitve, 05C15 Barvanja grafov in hipergrafov. Kljuˇcne besede: kromatiˇcni indeks, kubiˇcen graf, snark, poliedrska vloˇzitev, cvetni snark, Goldbergov snark, superpozicija, Kocholov snark. Zahvaljujem se mentorju prof. dr. Bojanu Moharju za pomoˇc pri izbiri snovi ter za nasvete in spodbudo pri raziskovalnem delu. Zahvaljujem se tudi vsem ostalim, ki so mi tem ˇcasu stali ob strani, ˇse posebej moji druˇzini in Barbari. Contents Abstract vii Povzetek ix 1 Introduction 1 1.1 Graphs................................ 1 1.2 Surfacesandgraph embeddings .................. 3 1.3 Snarks ................................ 7 1.4 Superposition ............................ 13 1.5 Embeddingsof cubicgraphs .................... 16 2 Genus of snarks 19 2.1 FlowersnarksandGoldberg snarks ................ 19 2.2 Toroidal snarks ........................... 27 2.3 The genus of P n . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4 Genusof thedotproduct . . . . . . . . . . . . . . . . . . . . . . 33 3 Polyhedral embeddings of snarks 37 3.1 Shortcycles ............................. 37 3.2 Small edge-cuts ........................... 40 3.3 Flowersnarks ............................ 47 3.4 Goldberg snarks. . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4 The defect of a graph 55 4.1 De.nition of defect and computer search . . . . . . . . . . . . . 55 4.2 Kochol snarks ............................ 62 4.3 DefectandGr¨unbaumconjecture . . . . . . . . . . . . . . . . . 66 Bibliography 74 Razˇsirjeni povzetek 77 xiii Chapter 1 Introduction Inthethesiswestudytheembeddingsofsnarksintoclosed surfaces. Thestudy is motivated by a conjecture of Gr¨unbaum which states that no snark has a polyhedral embedding into an orientable surface. This is a generalization of the Four Color Theorem and is one of the most interesting and long standing conjectures in graph theory. In the Introduction we de.ne basic graph theory and topological notions which are required in later chapters. 1.1 Graphs A graph G isa structurede.nedby apairof sets(V (G),E(G)). The set V (G) is a non-empty set and its elements are called the vertices of G. The set E(G) isa set of2-element subsetsof V (G)andits elements are called the edges of G. A set {u, v}, representing an edge, will be denoted by uv. We will investigate only .nite graphs, that is graphs for which the set V (G) is .nite. Also note that graphs are simple, that is there are no parallel edges and no loops. The number of vertices n = |V (G)|is called the order of the graph. For an edge e = uv in E(G)we call vertices u and v the ends of the edge e. If for vertices u, v . V (G)there is an edge e = uv . E(G)we say that the vertices u and v are adjacent and that the edge e connects vertices u and v. If v is an end of an edge e we say that v isincident with e andif vertices u and v are connectedby the edge e we say that v is a neighbor of u. The set of neighbors of a vertex v is denoted by N(v). The degree degG(v)of a vertex v . V (G)is the number of edges incident with v. The minimum degree of a vertex in the graph G is denoted by .(G) and the maximum degree of a vertex in the graph G is denoted by .(G). If all degrees of vertices in the graph G are equal to k, the graph is k-regular .A cubic graph is a 3-regular graph. Ageneralizationofa simplegraphis multigraph. Amultigraph M isde.ned 1 as a triple(V (M),E(M),.) where V (M) is the set of vertices, E(M) is the set of edges and . is a mapping which assigns each edge e . E(M)a pair of its ends, where we allow the ends to be the same vertex. In the latter case the edgeis called a loop.Weallowthattwoedgeshavethe sameendsinwhichcase we say that the edges are parallel. The degree of a vertex v in a multigraph is the number of edges such that v is its end where we count loops incident to v twice. Agraph H is a subgraph of agraph G if V (H). V (G)and E(H). E(G). If V (H)= V (G) then H is a spanning subgraph of G. If H is a subgraph of G this will be denoted by H . G. If V (H) . V (G) and if for each pair of vertices u, v . V (H)the edge uv . E(H)if and only if uv . E(G), thenH is an induced subgraph of G. A bijection . : V (G)› V (H)is an isomorphism if it maps adjacent ver­tices into adjacent vertices and non-adjacent vertices into non-adjacent ver­tices. If there exists an isomorphism between graphs G and H they are said to be isomorphic.Wewill notdistinguishbetweenisomorphicgraphs and will write G = H if G and H are isomorphic. A path Pn of length n - 1 is a graph with vertices V (Pn)= {v1,...,vn} and edges E(Pn)= {vivi+1 | i =1,...,n - 1}. Vertices v1 and vn are the ends of the path Pn and we say that the path Pn connects its ends. A cycle Cn of length n is a graph with vertices V (Cn)= {v1,...,vn}and edges E(Cn)= {vivi+1 | i =1,...,i -1}.{v1vn}. A subgraph P . G isomorphic to a path Pn is called a path in G and we say that P connects its ends in G. If for each pair of vertices u, v . V (G)there exists a path P in G connecting u and v we call the graph G connected. A maximal connected subgraph in G is called a connected component of G. A walk W in a graph G is a sequence of vertices (v1,v2,...,vn) where vertices vi and vi+1 are incident for i =1,...,n -1. Vertices v1,...,vn need notbe alldistinct. If v1 and vn are connected then W is called a closed walk in G.Instead ofde.ning awalkby a sequenceof vertices(v1,v2,...,vn)we will sometimesde.neit withthe sequenceof edges(e1,...,en-1), whereei = vivi+1, i =1,...,n -1. For a subset S . E(G) we denote by G - S the graph H with vertices V (H)= V (G)and with edges E(H)= E(G)\S. If the number of connected components of G -S is larger than the number of connected components of G we call the set S a cut. A minimal set S which is a cut is called a minimal cut. A connected graph G is k-edge-connected if every cut contains at least k edges. A cut of size k will be called a k-cut . For a subset U . V (G) we denote by G - U the graph H with vertices V (H)= V (G)\ U and in H two vertices are connected if and only if they are connected in G. A graph G is k-connected if every set U, for which the 1.2 Surfaces and graph embeddings graph G -U is not connected, contains at least k vertices. A cubic graph is k-connected if and only if it is k-edge-connected. A k-edge-coloring of a graph G is a mapping c : E(G) ›{1, 2,...,k} such that each pair of adjacent edges is mapped into distinct elements of {1, 2,...,k}. The minimum number k, for which there exist a k-edge-coloring of G, is the chromatic index, . ' (G), ofG. Vizingproved thefollowing theorem Theorem 1.1(Vizing). Every(simple) graph G satis.es .(G). . ' (G). .(G)+1 . Vizing’stheoremdividesgraphsintotwogroups. Graphsfor which. ' (G)= .(G) are called class 1 graphs and graphs for which . ' (G) =.(G)+1 are called class 2 graphs. As a special case cubic graphs of class 1 are those for which . ' (G)=3and cubicgraph of class2 arethoseforwhich . ' (G)=4. 1.2 Surfaces and graph embeddings In this section we give basic de.nitions for closed surfaces and graph embed-dings. We do not de.ne basic topological objects. We follow the book [1]. A closed surface is a connected compact Hausdor. topological space S which is locally homeomorphic to an open disc in the plane R2 . To simplify some arguments we will assume that graphs in this section do not have vertices of degree one or two. All results hold if we allow vertices of degree one or two also. Examples of surfaces are obtained as follows. Suppose F is a collection of polygons with all sides of length 1 which altogether have an even number of sides .1,...,.2k. Arbitrarily orient eachside .i bychoosing one ofits endpoints as the initial endpoint and choose a partition of sides into pairs. Form a topologicalspace S byidentifyingtwosidesineachpair sothattheorientations are respected(thatisfor apair .i,.j weidentify theinitial endpoint of .i with the initial endpoint of .j ). We get a compact Hausdor. topological space S and if S is connected then S is a surface. The sidesofpolygonsin F and their endpointsde.ne a multigraph G ' . We say that G ' is 2-cell embedded in the surface S. The collection of polygons F is called the collection of faces of G ' . Take a triangulated surface S and on a face T two disjoint triangles T1 and T2. If we orient the sides of T1 and T2 so that the orientations are clockwise, remove T1 and T2 from S and identify triangle T1 with T2 we obtain a surface S ' . We say S ' is obtained from S by adding a twisted-handle. If we orient the sides of T1 clockwise and the sides of T2 anticlockwise, remove T1 and T2 from S and identify triangles T1 and T2 we obtain a surface S '' . We say S '' is obtained from S by adding a handle. Let Q be a equilateral quadrangle in T . If we delete Q from T and identify opposite points on the boundary of Q we obtain a surface S ''' . We say S ''' is obtainedby adding a cross-cap to S. When we add handles and cross-caps we will usually use discs instead of triangles in T . Now start with a sphere S0 which is a tetrahedron. If we add n handles to S0 we obtain a surface Sn which is called the orientable surface of genus n. If we add n> 0 cross-caps to S0 we obtain a surface Nn which is called the non-orientable surface of genus n. The surface S1 is called the torus and the surface S2 is called the double torus. The surface N1 is called the projective plane and the surface N2 is called the Klein bottle. Instead of embedding graphs into the sphere we will usually embed graphs into the plane, which is equivalent by the stereographic projection of the sphere into the plane. The torus willbe represented as aquadrangle with corners a, b, c, d where we orient sides as ab, bc, dc, ad and identify sides ab and dc and sides bc and ad.A projective plane will be represented by a disc in which we identify antipodal vertices. It turns out that by adding handles and cross-caps to a sphere we can construct allpossibleexamplesof surfaces. Thisisestablishedby thefollowing theorem. Theorem1.2(Classi.cation of surfaces). Every surface S is homeomor­phic to precisely one of the surfaces Sn, n . 0 or Nn, n> 1. For surfaces Sn we de.ne the Euler characteristic .(Sn)=2-2n and for surfaces Nn we de.ne the Euler characteristic .(Nn) =2 - n. For arbitrary surface S we de.ne .(S) as the Euler characteristic of the unique surface Sn or Nn which is homeomorphic to S. For Sn we de.ne the orientable genus g(Sn)= n andfor Nn wede.ne the non-orientablegenus g~(Nn)= n. Asurface S is an orientable surface if it is homeomorphic to Sn for some n . 0 and it is a non-orientable surface if it is homeomorphic to some Nn, n> 1. The genus g(S) of an orientable surface S is n if S is homeomorphic to Sn. The non­orientable genus g~(S)of a non-orientable surface S is n, if S is homeomorphic to Nn. The Euler genus of an orientable surface S is o(S) =2g(S) and the Euler genus of a non-orientable surface N is o(N)= g~(N). A2-cell embedding of agraph G into a surface S isgraph G ' whichis2-cell embedded in S and isomorphic to G. Faces of the embedding of G are faces of G ' . 1.2 Surfaces and graph embeddings Let G be 2-cell embedded in S. Put a small disc Dv on each vertex v of G such that Dv intersects G only in v and edges incident with v and so that the intersection of Dv with each edge incident with v is a segment. Choose an orientation of the boundary of Dv . Intersections of edges {e1,...,dk}incident with v and the boundary of Dv de.ne a clockwise ordering of edges incident with v around v. This ordering de.nes a permutation .v of edges incident with v for which .v (e)= e ' if e ' follows e in the ordering. For an edge e = uv we say that orderings .v and .u are consistent if for an orientation of e the discs Dv and Du with orientations whichde.ne .v and .u cross e onefromleft to right and the other from right to left. If .v and .u are consistent than we set .(e) = 1 and if they are not consistent we set .(e)= -1. The mapping . is called the signature of edges (see Figure 1.1). It turns out that if S is orientable then we can choose the orderings around vertices so that for each edge e . E(G)we have .(e)=1. Denote by . = {.v | v . V (G)}the collection of clockwise permutations around vertices of the embedded graph G.Thepair. =(., .)is is called a rotation system of the embedded graph G. Two rotation systems . and . ' are equivalent if . ' can be obtained from . by a sequence of transformations wherein eachtransformation we reversethe clockwise ordering around a vertex v and change the signs of all signatures of edges incident with v. It turns out that a 2-cell embedding of G is completely determined by its rotation system and that each rotation system de.nes a 2-cell embedding. A rotation system is called a combinatorial embedding. From now on whenever we say that . is an embedding of agraph G wemeanthat.isarotation systemwhichde.nes the embedding. A sequence of vertices of and embedded graph G which appears along a face of G is called a facial walk. If all vertices along W are distinct then W is called a facial cycle. Given a rotation system . of G the collection of facial walks is obtained as follows. Choose a vertex v0 and an edge e = v0v1 incident with v0. Traverse the edge e. From v1 continue on the edge .v1 (e) and repeat this until an edge f = vi-1vi is traversed from vi-1 to vi for which .(f)= -1 (it could be that f = e). Now traverse the edge which follows f in the anticlockwise order around vi, .v-i 1(f), andrepeat this until an edge with negative signature is traversed again. From there on traverse edges in clockwise order around vertices and so on. Repeat this until e is traversed again in the same order from v0 to v1. When this happens we have obtained a facial walk of the embedding of G.Togetotherfacial walksrepeatthisprocedure starting with another vertex u0 and an edge u0u1 which has not been traversed from u0 to u1.Whenno such edgesremain(thatisall edgeshavebeentraversedinboth directions) we get all facial walks of the embedding. Two equivalent rotation systems de.ne the same collection of facial walks. A rotation system is determined by the collection of facial walks. Suppose F is a collection of facial walks. Choose a vertex v and an edge e1 incident with v. There is a facial F1 walk which contains the edge e1. This walk also contains another edge incident with v, say e2, so that the edges e1 and e2 are consecutive along F1. There is a facial walk F2 which contains e2 and a third edge e3 such that e2 and e3 are consecutive along F2. We continue this until we come back to the edge e1. We de.ne the clockwise order around v to be e1,e2,.... Once we have clockwise orderings around each vertex we can de.ne the signaturesof edges. Ofcoursenot every collectionof walksisacollectionof facial walks of some embedding. For a cubic graph a su.cient condition that a collection of closed walks F is a collection of facial walks of some embedding is that each path of length 3 appears along exactly one walk in F. Suppose we have an embedding . of a graph G into a surface S. Denote with F (G) the collection of facial walks of the embedding. The number of facial walks can be determined by the following relation. Proposition 1.3(Euler formula). The following equation holds |V (G)|-|F (G)|+ |F (G)|=2-o(S). If . is an embedding of G into an orientable surface S we de.ne the ori­entable genus of. as g(.) = g(S). If . is an embedding of G into a non­orientable surface S we de.ne the non-orientable genus of. as~g(.)= g~(S). The (orientable)genus of a graph G is the minimum g(G)= {g(.) | . orientable embedding of G} 1.3 Snarks and the non-orientable genus of a graph G is the minimum g~(G)= {g~(.) | . non-orientable embedding of G}. Let . be an embedding of G into a surface S. We de.ne the geometric dual G* of G in S as follows. The vertices of G* correspond to facial walks of the embedding of G. The edges of G* are in bijective correspondence with the edges of G. An edge e * joins verticesw and v in G* if the edge e appears on facial walks corresponding to vertices w and v. For a facial walk W = e1e2 ··· en de.ne the rotation around the vertex w in G* corresponding to W as .w =(e1,e2,...,en). We de.ne .(e *) = 1 if facial walks W and V corresponding to vertices w and v, e = vw, traverse e in opposite directions and .(e *)= -1 otherwise. It is easy to verify using the Euler formula that . and .* are embeddings into the same surface. Note that for a graph G the dual G* canbe a multigraph(thatisthere couldbeparallel edges orloopsin G*). A graph G embedded into a surface S such that all facial walks are of length 3 is called a triangulation of S. The geometric dual of a triangulation is a cubicgraph(seeFigure1.7). 1.3 Snarks In this thesis we will mostly be interested in cubic graphs of class 2. Before we start with the introduction to class 2 cubic graphs we state a very useful Lemma about 3-edge-colorings of cubic graphs. Lemma 1.4(Parity lemma). Let c be a3-edge-coloring of a cubicgraph G and S a cut in G. Denote by Si the set of edges in S colored with color i. Then |S1|.|S2|.|S3|.|S| (mod 3). Snarks are non-trivial cubic graphs of class 2. A cubic graph G of class 2 is trivial if thereis a reduction of G to a smaller snark or if there is an obvious obstruction for G whichprevents it to have a3-edge-coloring. We now explain what are trivial class 2 cubic graphs which will be excluded in the de.nition of snarks. Suppose S = {e}isacutof size1inacubicgraph G. The edge e is called a bridge of G. If c is a 3-edge-coloring of G then we can assume that c(e)=1 which implies that |S1| = 1 and |S2| = |S3| = 0 which is a contradiction to the Parity lemma 1.4. Therefore if a cubic graph contains a bridge it can not be 3-edge-colorable. We will therefore require that snarks must be bridgeless graphs. Suppose S = {e, f}is a2-cutin abridgeless cubicgraph G. Let G -S be composed of graphs G1 and G2. Suppose e = v1v2 and f = u1u2 and suppose that v1,u1 . V (G1)and v2,u2 . V (G2). Add edges u1v1 to G1 obtain a cubic graph G ' and u2v2 to G2 to obtain a cubic graph G ' 2. If G ' and G ' are 3­ 1 12 edge-colorable then we have a coloring c ' of graphs G ' 1 and G2 ' and further we can assume that c ' (v1u1)= c ' (v2u2)= 1. Now we de.ne a coloring c of G as follows. For an edge g ..{e, f} de.ne c(g)= c ' (g) and c(e)= c(f) =1. It is easy to check that c is a 3-edge-coloring of G. Therefore if there is a 2-cut in a class 2 cubic graph G, we can reduce G to smaller cubic graphs G1 and G2 such that at least one of them is of class 2. Therefore we will require that snarks are 3-connected. A cut S in G such that G - S has at least two components containing a cycle is called a cyclic cut. A graph is cyclically k-edge-connected if every cyclic cut contains at least k edges. Suppose that G is a 3-connected cubic graph containing a cyclic cut S = {e1,e2,e3}. Then G - S consists of two connected components G1 and G2 each containing a cycle. Graphs G1 and G2 each contain three vertices of degree 2 which are the ends of edges in S. If we add a vertex v1 to G1 and connect it to the degree 2 vertices in G1 and add a vertex v2 to G2 and connect it to the degree 2 vertices in G2 we get cubic graphs G ' 1 and G2' . Suppose we have a 3-edge-coloring c ' of G1 and G2. We can assume that c ' (v1ui)= c ' (v2wi)= i where ui and wi are the ends of ei. We can de.ne a coloring c of G by de.ning c(e)= c ' (e)if e ..{e1,e2,e3}and c(ei)= i. This is a 3-edge-coloring of G. So if there is a cyclic 3-edge-cut in a class 2 graph G, we can reduce G to smaller cubic graphs G ' 1 and G ' 2 at least one of which is of class 2. Therefore we will require that snarks are cyclically 4-edge-connected. Note that a 3-connected cubic graph is cyclically 4-edge-connectedif every 3-cut separatesthegraphintotwocomponents,one of which is a vertex. Suppose we have a cubic graph G which contains a 3-cycle C3 on vertices 0,1,2(seeFigure1.2). If we replace C3 with a vertex v we obtain a cubic graph G ' . Suppose c ' is a 3-edge-coloring of G ' . De.ne a mapping c : E(G)› {0, 1, 2}as follows. If an edge is not incident with any of 0, 1, 2 then c(e)= c ' (e). Further de.ne c(vii)= c(vi+1vi+2)= c ' (viv), i =0, 1, 2, where incides are modulo 3. Then c is a 3-edge-coloring of G. We see that if G is of class 2 then G ' is also of class 2. Therefore if we have a 3-cycle in a class 2 cubic graph we can reduce it to a smaller cubic graph of class 2. We will therefore require that snarks have no cycles of length 3. Suppose wehave a cubicgraph G which contains a4-cycle C4 on vertices0, 1,2,3(seeFigure1.3). Ifwe replace C4 with two edges e0 = v0v1 and e1 = v2v3 we obtain a cubic graph G ' . We can assume that G ' is bridegles, otherwise we add edges v0v3 and v1v2. Suppose c ' is a 3-edge-coloring of G ' . De.ne a 1.3 Snarks v2 v2 2 v 01 v0 v1 v0 v1 Figure 1.3: Removing a 4-cycle from a graph. mapping c : E(G)›{0, 1, 2} as follows. If an edge is not incident with any of0,1,2,3 then c(e)= c ' (e). If c ' (e0)= c ' (e0) = 1 then color c(vii) =1, c(01)= c(23)=2and c(12)= c(30)= 3. Otherwise c(e0)=1and c(e1)=2 and we color c(v00) = c(v11) = c(23) = 1, c(v22) = c(v33) = c(01) =2and c(03)= c(12)= 3. In both cases c is a 3-edge-coloring of G. Therefore if we have a 4-cycle in a class 2 cubic graph we can reduce it to a smaller cubic graph of class 2. We will therefore require that snarks have no cycles of length 4. The length of the shortest cycle in G is called the girth of G. Since we will not allowcyclesoflength3 or4in snarks, snarkswillberequired tohavegirth at least 5. We now ready to give the formal de.nition of a snark. A snark is a3-connected, cyclically 4-edge-connected cubicgraph of class2 withgirth at least 5. The smallest snark is the Petersen graph found by Petersen at the end of 19th century[2]. ThePetersengraphis one ofthe mostimportantgraphsin graph theory. It is shown in Figure 1.4. Although the Petersen graph was found very early .nding other snarks proved to be a di.cult task. This is where snarks get their name. The name comes from the song The Hunting of the Snark by Lewis Carroll in which snarks are monsters which are very hard to .nd. The Petersen graph is the only snark on 10 vertices. The are no other snarks on less than 18 vertices. In 1940’s Croatian mathematician Blanuˇsa discovered two snarkson18 vertices,nowknownasBlanuˇsa snarks[3]. They are shown in Figure 1.5 and are the only two snarks on 18 vertices. The.rstin.nitefamily of snarkswasdiscoveredin1970’s. Isaacspublished a paper [7] in which he describes a dot product of graphs which constructs a snark G as a product of two smaller snarks G1 and G2. Although the dot product is attributed to Isaacs the construction was published earlier by a Russian mathematician Titus but this paper is unknown to many people working on snarks. The dotproduct ofgraphs G1 and G2 is constructed as follows. Choose an edge e = uv in G1 and two non-adjacent edges f1 = v1v2 and f2 = v3v3 in G2. Denote the neighbors of u distinct from v with u1 and u2 and the neighbors of u distinct from v with u3 and u4. The dot product G = G1 · G2 of graphs G1 and G2 is constructed by removing the vertices u and v from G1 and edges f1 and f2 from G2 and adding edges viui for i =1, 2, 3, 4. Note that if a 1.3 Snarks graphisadotproductoftwo smallergraphs,thenitis(atmost) cyclically 4-edge-connected. The cut consisting of edges added to G1 and G2 is called the product cut. It is easy to prove using the Parity lemma that if G1 and G2 are snarks then G is also a snark. A reverse of previous statement also holds. If G is a snark with a cyclic 4-cut S thentherearetwo smallergraphs G1 and G2 so that G is obtained as a dot product of G1 and G2, at least one of G1 and G2 is a snark and that S is the product cut of the dot product. It is clear from the de.nition of the dot product that the dot product of G1 and G2 is not uniquely de.ned by G1 and G2 but it depends on the choice of edges and vertices in G1 and G2. If we take two copies of the Petersen graph for G1 and G2 there are two possible non-isomorphic dot product we can construct. These two non-isomorphicdotproducts are exactlytheBlanuˇsa snarks. By starting with the Petersen graph and constructing bigger snarks from smalleritispossibletoconstructthe.rstin.nity family of snarks. All snarks in this family are cyclically 4-edge-connected. Isaacs also described an in.nite family of cyclically 6-edge-connected snarks which are known as .ower snarks. A .ower snark J2k+1, k> 1, is a snark on vertices V (J2k+1)= {ai,bi,ci,di | i =0,..., 2k} and with edges E(J2k+1)= {aiai+1,aibi,bici,bidi,cidi+1,dici+1 | i =0,..., 2k} where indices are modulo 2k + 1. The subgraphs Yi induced on vertices {ai,bi,ci,di} are called tiles of .ower snarks. The .ower snark J2k+1 is ob­tainedbyputting tiles Yi on a circle and then appropriately adding three edges between tiles Yi and Yi+1 for i =0,..., 2k. The .ower snark J5 is shown in Figure 1.6. We note that thegraph J3 isof class2butisnot a snarksinceit containsa 3-cycle. If we remove the 3-cycle in J3 and replace it with a vertex, we obtain the Petersen graph. Anotherwellknownin.nitefamily of snarkswasgivenbyGoldberg. Gold­berg snark G2k+1, k> 1, is the graph with vertices V (G2k+1)= {ai,bi,ci,di,ei,fi,gi,hi | i =0,..., 2k} and with edges E(G2k+1)= {aiai+1,aibi,bici,bidi,ciei,cigi, difi,dihi,gihi,eifi,fiei+1,gihi+1 | i =0,..., 2k} 1.4 Superposition where indices are modulo 2k + 1. The subgraphs Ti induced on vertices {ai,bi,ci,di,ei,fi,gi,hi} are called tiles of the Goldberg snarks. Similarly as .ower snarktheGoldberg snarksareobtainedbyputtingtiles Ti on a circle and appropriately adding three edges between tiles Ti and Ti+1 for i =0,..., 2k. The Goldberg snark G5 is snown in Figure 1.6. If we do not require that there are an odd number of tiles, we can de.ne graphs Jk and Gk for all k . 3. Graphs J2k and G2k are of class 1. Snarksdescribed sofarallhavegirth at most6(.ower snarks J2k+1, k> 1, have girth 6 and Goldberg snarks have girth 5). If there exist snarks with arbitrary largegirthhasbeenanopenquestionfor sometime. In1980Jaeger andSwart[10] conjecturedthat all snarkshavegirth at most6. Thisconjecture wasdisprovedbyKochol[17]in1997 whenhe constructed anin.nitefamily of snarks which contain snarks with arbitrary large girth. Kochol’s construction called superposition is the most general construction of snarks known. A special class of snarks constructed by superposition for which Kochol proved that it contains snarks with arbitrarily large girth is called Kochol snarks. Thereare someotherconstructionsofsnarksknown. ForexampleGoldberg snarks are a special case of the Loupekhine construction of snarks. Also all snarks with at most28 vertices areknown[24]. 1.4 Superposition We give a short description of the superposition of graphs. Superposition is the most general known construction of snarks. It generalizes many previ­ously known constructions, for example the dotproduct. It was introducedby Kocholin[17] wherehedisprovedthegirth conjecturefor snarks. Thegirth conjecture statedthat snarkshaveboundedgirth(inparticularthatforany snark G, the girth of G is at most 6). Kochol proved that a special class of snarksobtained asa superpositionof thePetersengraph contains snarkswith arbitarilly large girth which disproves this conjecture. Superpositionisaconstructionof snarksinwhich wereplacetheedgesand vertices of snarks by cubic graphs (with pending edges) called supervertices and superedges.Therearealmostnorequirementsfor supervertices,all thatis requiredisthat superedges satisfy certainproperties. Becausetherearealmost norequirementsfor superverticeswecanconstruct avery richfamily of snarks using superposition. Wegiveashortdescriptionof the superposition,formore details see[17]. A multipole M =(V, E, S) consists of a set of vertices V , edges E and semiedges S. A semiedge s is incident to one vertex v and denotedby s =(v). We assumethatthedegrees of verticesin a multipole are all3(thedegree of 1.4 Superposition a vertex v in a multipole is the number of edges and semiedges incident with v). A(k1,...,kn)-poleis a multipole(V, E, S) with a partition of semiedges into sets S = S1 .· ··. Sn with |Si|= ki, i =1,...,n. The sets S1,...,Sn are called the connectors of the multipole. A(k1,k2)-poleis calleda superedge and a(k1,k2,k3)-pole is calleda supervertex. A(1, 1, 1)-pole consisting of a single vertex v and three semiedges incident with v is called a trivial supervertex. Let G be a snark. We remove two non-adjacent vertices v and u from G and replace all edges vxi incident with v with semiedges(xi),i =1, 2, 3, and all edges uyi with semiedges(yi),i =1, 2, 3. We de.ne S1 = {(x1), (x2), (x3)} and S2 = {(y1), (y2), (y3)} and we obtain a (3, 3)-multipole with connectors S1 and S2 called a proper superedge. We say we obtained this superedge by removing vertices v and u from G. An empty multipole will be considered as a special(1, 1)-multipole and a proper superedge. For a broader de.nition of aproper superedge see[17]. Let G =(V, E) be a cubic graph. To each vertex v . V we assign a supervertex S(v)and additionally to each edge incident to v we assign one of the connectors of S(v). To each edge xy . E we assign a(proper) superedge E(xy)and additionally we assign one of the connectors to x and the other to y (unlessE(xy)is an empty multipole). Assume that for each edge e = xy . E the following holds. If E(xy) is an empty multipole, then the connectors assigned e in supervertices S(x) and S(y) have cardinality 1. Otherwise the connector assigned to edge e in supervertex S(x)(S(y))has the same cardinalityas the connector assigned to x (y)in superedge E(xy). Wecanthenconstruct anewgraph asfollows. If the superedgeassigned to e = xy isanempty multipole,thenweremove semiedge(v)in the connector of S(x)assigned to e andthe semiedge(u)in the connector of S(y)assigned to e and add an edge uv. Otherwise we have semiedges {(u1), (u2), (u3)} in the connector of S(x) and semiedges {(x1), (x2), (x3)} in the connector of e assigned to x. We remove them and add edges {u1x1,u2x2,u3x3}and do the same for vertex y. By repeating the procedure for all edges e . E weget a cubic graph G ' called a superposition of G. If to all edges we have assigned proper superedges, the graph G ' is called a proper superposition of G. Kocholproved thefollowing result[17] Theorem 1.5. For a snark G a proper superposition G ' is a snark. Snarks areimportantingraph theorybecause they appear aspossible min­imal counter-examplesfor someof themostimportant openproblemsingraph theory. One of the most interesting open problems is the Cycle Double Cover conjecture. Acollection C of cyclesin agraph G is calledadouble coverif every edge of G is contained in exactly two cycles from C. The Cycle Double Cover conjecture states that for every 2-edge-connected graph there exists a cycle double cover. It is not too hard to show that every minimal counter-example to this conjecture would be a cubic graph. Now suppose that c is a 3-edge­coloring of a cubic graph G. A subgraph Hi,j induced on the edges colored with colors i and j,1 . i 3, have polyhedral embeddings into any (orientable or non-orientable) surfaces. We also show that the conjecture is true for Goldberg snarks and Kochol snarks. BesidestheSzekeres’paper[5], not muchhasbeenpublished aboutpoly­hedral embeddingsof snarks. Tinsley andWatkinsstudied thegenusof.ower snarks[12]. They observethatthegenusof snarksthey studyincreaseswith the order of the graph. In the next chapter we extend their results. We .nd the genus of .ower snarks and Goldberg snarks and prove some results about the genus of dot products of the Petersen graph. In the third chapter we study polyhedral embeddings of .ower snarks and Goldberg snarks into ori­entable and non-orientable surfaces. We show some obstructions for existance ofpolyhedral embeddingsand constructpolyhedral embeddingsof snarksinto non-orientable surfaces. In the last chapter we prove that Kochol snarks do nothavepolyhedral embeddingsintoorientable surfaces. Wede.nethedefect of agraph whichis a measureforhowfar agraphisfromhaving apolyhedral embedding into an orientable surface and prove some results connecting the Gr¨unbaum conjecture, defect and resistance of cubic graphs. Chapter 2 Genus of snarks In this part of the thesis we give some results about the genus of snarks. Thegenusof snarkshasbeen studiedinapaperofTinsley andWatkins[12] in which they determine the orientable genus of .ower snarks. They give an upperboundfortheorientablegenusofGoldberg snarksand makeaconjecture aboutthegenus ofdotproducts of thePetersengraph. Based onthese results they observethatthegenusof the snarksthey studiedincreaseswith theorder of the snark. The method Tinsley and Watkins used to prove their results on the genus of J2k+1 are topological. We .rst prove their result on the orientable genus of J2k+1 using a combinatorial method. This method extends to the non­orientable case aswell. Using the same idea we determine orientable and non­orientable genus of Goldberg snarks. Next we study the orientable genus of dot products. We .rst disprove the conjecture of Tinley and Watkins about the orientable genus of P n . We show thatthere arein.nitely manygraphs P n which can be embedded in the torus. Further for each g,1 . g . n, we show that there is a product P n such that the orientable genus of P n is equal to g. Finally we give tight bounds for the orientable genus of a dot product of two cubic graphs. 2.1 Flower snarks and Goldberg snarks Tinsley and Watkins determined the orientable genus of .ower snarks. They usetopological methodstoprovethelowerbound and used adi.erent approach forthenon-orientablegenus. Inthis sectionwegiveashortcombinatorialproof of their results which worksforboth orientable and non-orientablegenus. The proof works by counting arguments and uses the Euler formula. A similar approach also works for Goldberg snarks. 19 Theorem 2.1(Tinsley, Watkins). Theorientablegenusofthe.ower snark is g(J2k+1)= k and the non-orientable genus is g~(J2k+1)=2k -1. Proof. An embedding of J2k+1 inanorientable surfaceofgenus k isdescribed by a list of facial cycles • a0a1 ··· a2k, • c0d2kc2k-1d2k-2 ··· c1d0c2k ··· d1c0, • d0b0c0d1b1c2 ··· d2kb2kc2kd0, • Fi = aibidici+1bi+1ai+1ai for i =0,... 2k, which gives g(J2k+1). k (see also Figure 2.1which show an embedding of J5 into an orientable surface of genus 2). 2. Anon-orientable embedding of J2k+1 ina surfaceofgenus2k-1isdescribed by a list of facial cycles 2.1 Flower snarks and Goldberg snarks • a0a1 ··· a2k, • c0d1b1c1d2b2c2 ...d2k-1b2k-1c2k-1d2kc0, • c0d1c2d2 ...d2k-1c2kb2kd2kc0, • d0c1d2c2 ...d2kb2kc2kd0, • Fi = aibidici+1bi+1ai+1ai for i =0,... 2k, which gives the upper bound ~g(J2k+1) . 2k - 1. See also Figure 2.2 which shows the embedding of the .ower snark J5 into the non-orientable surface N3. By contracting each tile Yi of J2k+1 to a vertex i weget a cycle Q of length 2k +1. Each facial walk W in an embedding . of J2k+1 induces a walk W ' in Q. We de.ne the winding number w(W )of W to be the winding number of W ' in Q. A facial walk in . is local if w(W )is zero and global otherwise. We show that in the embedding of . we can have at most 2k +1 local facial walks. For each local facial walk W there exists an index i, such that W contains apath P = x0x1 ...xl-1xl, where vertices x0 and xl are in the tile Yi-1 and vertices x1,...,xl-1 are in the tile Yi. To the walk W we assign the vertex i of Q. There arethreepaths of theform x0x1bi where x0 is in the tile Yi-1. Since each walk assigned to the vertex i contains two such paths and each path of length tree can appear at most once along facial walks of ., we see that to each vertex of C2+1 we assigned at most one facial walk. So we can have at most 2k +1 local facial walks in the embedding of J2k+1. In the embedding of J2k+1 we can either have 6 global facial walks or at most 2k +1 local facial walks and 4 global walks. This implies that there are at most 2k +5 facial walks in an embedding of J2k+1. Suppose . is an embedding of J2k+1 into a non-orientable surface of mini­mum possible genus ~g(J2k+1). By Euler formula 2-g~(J2k+1)= |V (J2k+1)|-|E(J2k+1)|+ |F.(J2k+1)| . 4(2k +1) -6(2k +1)+2k +5 =3-2k the non-orientable genus is ~g(J2k+1). 2k -1. Suppose .is an embedding of J2k+1 into an orientable surface of minimum possiblegenus g(J2k+1). Since |V (J2k+1)|=4(2k +1) and |E(J2k+1)|=6(2k + 1), by Euler formula |V (J2k+1)|-|E(J2k+1)|+ |F.(J2k+1)| =2 - 2g(J2j+1), there are an even number of facial walks in .. Therefore there can be at most 2k +4 facial walks in .. Now the Euler formula 2-2g(J2k+1)= |V (J2k+1|-|E(J2k+1|+ |F.(J2k+1)| . 4(2k +1) -6(2k +1)+2k +4 =2-2k implies that g(J2k+1). k. The sameargumentatsalsoworkforgraphsJ2k.Wecan showthatinevery embedding of J2k there can be at most 2k. If there are 2k local facial walks, then there are four global facial walks. Since every embedding can have at most 2k +4 facial walks we get a lower bound for genera of J2k. Theorem 2.2. Theorientablegenusof the .owergraph J2k is g(J2k)= k -1 and the non-orientable genus is g~(J2k)=2k -2. Proof. The lower bound is obtained in the paragraph before the theorem. From Figure 2.4 it is easy to obtain embeddings of J2k into non-orientable surfaces of genus 2k - 2. An embedding of J2k into an orientable surface of genus k -1 is given by the following list of facial cycles: • a0a1 ··· a2k-1, 2.1 Flower snarks and Goldberg snarks • d0c2k-1d2k-2c2k-3 ...d0, • c0d2k-1d2k-2d2k-3 ...c0, • d0b0c0d1b1c1 ...d2k-1b2k-1c2k-1d0, • Fi = aibidici+1bi+1ai+1ai for i =0,... 2k -1, Tinsley and Watkins obtained an upper bound for the orientable genus of Goldberg snark G2k+1 by showing an embedding into the orientable surface of genus 2k. Using ideas similar to those used in the proof of the previous theorem we show that this bound is the correct value for the orientable genus of G2k+1. We also determine the non-orientable genus of G2k+1. Theorem 2.3. The orientable genus of the Goldberg graph is g(Gk)= k -1 and the non-orientable genus is g~(Gk)= k. Proof. We .rst look at orientable genus. An embedding of the Goldberg graph Gk in the orientable surface of genus k is described by facial cycles • a0a1 ··· ak-1a0, • Ci = aibidifiei+1ci+1bi+1ai+1ai for i =0,...,k -1, • Di = bicigihidibi, for i =0,...,k -1, • f0e0fk-1ek-1 ··· f1e1f0, • h0g0h1g1 ··· hk-1gk-1h0, • f0d0h0g2kck-1ek-1fk-2dk-2hk-2 ··· g0c0e0fk-1dk-1hk-1 ··· g1c1e1f0. See also Figure 2.3. For thelowerboundfor the orientablegenus we use theEuler formula. We have |V (Gk)|=8k, |E(Gk)|= 12k and in the embedding into the orientable surface of genus k there are 2k + 2 facial walks. We show that if . is an orientable embedding of Gk, then there are at most 2k +2 facial walks in ., which gives the lower bound k for the genus of the surface. We group facial walks in the embedding . of Gk into three groups. A facial walk is short if it is contained in a tile Ti of Gk and long otherwise. By contracting tiles Ti of Gk into vertices i we obtain a cycle Q of length k. Each facial walk W in the embedding . de.nes a walk W ' in Q. The winding number of W ' in Q de.nes the winding number w(W ) of W . A long facial walk is local if the winding number is zero and global otherwise. With this we have grouped facial walks of . into three groups: short and long local walks and global walks. We show that we can have at most 2k +2 local walks. To each local walk we assign a vertex in Q as follows. To a short walk in a tile Ti we assign the vertex i. If W is a long walk, there exists an index i and a sub-walk P = x0x1 ...xl-1xl on W such that x0 and xl are in the tile Ti-1 and all vertices x1,...xl-1 arein the tile Ti, since otherwise the winding number of W could not be zero. To W we assign the vertex i in Q (if there are more than one possibilities for i we arbitrarily choose one of them). We now prove that to each vertex i we can assign at most two facial walks which implies that we have at most 2k local walks. 2.1 Flower snarks and Goldberg snarks Suppose wehave assigned threelonglocal walks W1, W2 and W3 to i. Since there are only three edges from tile Ti-1 to Ti, all are contained twice in walks W1, W2 and W3, andinparticularedge ai-1ai is contained twice in them. But since we assigned all of W1, W2 and W3 to i we see that if W1 contains ai-1ai, it must contain ai-1aibi. Butin the embedding.itis notpossible that apath of length 3 appears twice along facial walks in .. Suppose wehave assigned threelocal walks W1, W2 and W3 to i, where W1 is short and W2 and W3 are long. There are two possibilities for W1. Either it contains the cycle higicibidihi or higicieifidihi (the case when it contains dibicieifidi is symmetric to the .rst case). Suppose W1 contains higicieifidihi. We have facial walks which contain paths hi-1gihigi+1, ei-1fieifi+1 and ai-1aiai+1. This is a contradiction with the fact that ai-1ai, ei-1fi and hi-1gi appear twice on each of W2 and W3. Suppose that the consistent orientation of facial walks W1 contains the path higicibidihi.Wehavefacialwalkswhichcontainpaths(in someorientation) hi-1gihigi+1 and ai-1aiai+1. It follows that both W2 and W3 contain the edge ei-1fi. Now W2 must contain ei-1fidibiaiai-1. The walk W3 must contain edges fiei-1 and gihi-1 in these orientations. But this is a contradiction. Finally assume that we have assigned two short local facial walks W1 and W2 to i. Since a short local walk at i contains one of three cycles higicibidihi, dibicieifidi or higicieifidihi it follows that at least one path of length 3 is contained twice along facial walks of the embedding, which is a contradiction. So in an embedding of Gk there can be at most 2k local facial walks. In particular we have shown that there can be at most k short local walks in an embedding of Gk. Now suppose we have an embedding . into an orientable surface of genus less than k -1. By Euler formula 2-2g(Gk)= |V (Gk)|-|E(Gk)|+ |F (Gk)| =8k -12k + |F (Gk)| = |F (Gk|-4k we get |F (Gk)|=4k +2 -2g(Gk). 4k +2 -2(k -2) =2k +6. Since at most 2k of them can be local walks, we have at least 6 global walks. Since eachglobal walk contains atleast one edge connecting thetile Ti-1 with the tile Ti and there are three edges connecting tile Ti-1 and Ti, we see that no local walk can contain an edge between two tiles. So all local walks are short. But we can have at most k short local walks, a contradiction. We have shown that the genus of Gk is at least k -1. We now prove that the non-orientable genus of the Goldberg snark is g~(Gk)= k. An embedding of Gk into a non-orientable surface of genus k is described by facial cycles • a0a1 ··· ak-1ka0, • Ci = aibidifiei+1ci+1bi+1ai+1ai for i =0,...,k -1, • Di = bicigihidibi for i =0,...,k -1, • Ei = fiei+1fi+1di+1hi+1gicieifi for i =0,...,k -1, • Fi = h0g0higi ...hk-1gk-1h0. An embedding of G5 into the non-orientable surface of genus 5 is shown in Figure 2.4. Is is easy to see how to get an embedding of arbitrary Gk into a non-orientable surface of genus k. To prove the lower bound we show that in a non-orientable embedding of G2k+1 there can be at most 3k local facial walks which will give an upper bound for the number of facial walks to be 3k +2. This implies that thegenus of the surface is at least k. Again as before we can assign to each local facial walk a vertex of Q. We show that to each tile Ti we can assign at most three local facial walks. As in the case of the orientable embedding there can be at mostone shortfacial cycleineach tile. If weassigned threelonglocal walksto a tile Ti, then all three edges between tiles Ti-1 and Ti must appear on them, each twice. But this implies that the path ai-1aibi is contained in two facial walks, which is a contradiction. To each tile we can assing at most three local facial walks(one short and twolong),whichimpliesthattherecanbeat most 3k local facial walks. If we assigned three local facial walks to any tile, then there can be at most two global facial walks. So the biggest possible number of facial walks is 3k +2 and by Euler formula 2-g~(Gk) = 8k -12k + |F (Gk)| . 8k -12k +3k +2 =2-k we have ~g(Gk). k. Inparticularcase,thelasttheorem statesthatforGoldberg snarkswehave g(G2k+1)=2k and ~g(G2k+1)=2k +1. 2.2 Toroidal snarks 2.2 Toroidal snarks Let P n denote adotproduct of n copies of thePetersengraph. In[12] authors proposed a conjecture, that a graph P n has orientable genus precisely n -1. In the construction of P 2 there are two non-equivalent ways to choose edges e1 and e2 in the .rst copy of P , sotherearetwonon-isomorphicdotproductsof twocopiesof thePetersengraph(which aretheonlytwo snarkson18 vertices). Thepreviousconjecturewasdisprovedin[21],whereitwas shownthatoneof the twopossibledotproducts P 2 hasorientablegenus2, sothatthegenuscan be bigger than conjectured. Inthis sectionwe showthatforeverypositiveinteger n adotproduct of n copies of the Petersen graphs exists, which can be embedded in the torus and hasthereforegenus1, sothereexistsandin.nitefamilyof counter-examplesfor which thevalueof thegenuscanalsobe(much) smallerthantheconjectured value. We also show that for each g there are in.nitely many snarks with orientable genus precisely g. Let G1 be a cubic graph embedded into an orientable surface Sg and G2 be a cubic graph embedded in the torus T . Let e1 = x1x2 and e2 = x3x4 be two edges of G1 such that in the embedding of G1 there are two facial walks C1 = x1x2P1x3x4P2x1 and C2 = x2x1P4x4x3P3x2. Then we say that edges e1 and e2 satisfyproperty P. Letf = uv be an edgeinG2 suchthat the neighbors of u, distinct from v, are y1,y2, the neighbors of v, distinct from u are y3,y4 and in the embedding of G2 there are distinct facial walks D1 = y1uvy4R4y1, D2 = y3vuy2R3y3 and D3 = y2uy1R2y4vy3R1y2. Lemma 2.4. Let G1 and G2 be as above. Then a dot product G = G1 · G2 exists which has an embedding into the surface S1. Furthermore, the edges e ' i = xiyi and e ' j = xj yj in G have property P. Proof. Let G1 and G2 be embedded as in the Lemma. Let G be the dot productasdescribedintheparagraph abovetheLemma. Wede.nethe embed­ding of G by specifying vertex rotations. Denote with X the set {xi,yi | i = 0, 1, 2, 3, 4}. The rotations atverticesin V (G)\X are the same as the rotations in the embeddings of G1 and G2. The rotations at vertices in X are the same as the rotations in the embeddings of G1 and G2 where we naturally replace the deleted edges with the added ones. This is clearly an embedding into an orientable surface. Toprovethatthis surfaceis S, we count thefacial walks of the embedding. Thefacial walks whichdo not contain any of the verticesfrom X are facial walks in the embedding of G1 or G2. The facial walks, which con­tain vertices from X are x2P1x3y3R1y2x2, x1y1R2y4x4P2x1, x2P1x3y3R1y2x2 2.2 Toroidal snarks and x1P4x4y4R4y1x1. So we have replaced .ve facial walks with four. We have |V (G)| = |V (G1)|+ |V (G2)|-2, |E(G)| = |E(G1)|+ |E(G2)|-3 and |F (G)|= |F (G1)|+ |F (G2)|-1. So |V (G)|-|E(G)|+ |F (G)| = |V (G1)|-|E(G1)|+ |F (G1)|+ |V (G2)|-|E(G2)|+ |F (G2)|-1 = 1+2-2g -1 =2-2g which shows that this is an embedding in Sg . It is also easy to see that edges x1y1 and y4x4 satisfy the property P Corollary 2.5. For every positive integer n there exists a dot product of n copies of the Petersen graph, that can be embedded in the torus. Proof. An embedding of the Petersen graph in the torus is shown in Figure 2.6. Itis easy to check thatif we take the edges x1x2 and x3x4 in one copy and the edge uv in the other, the conditions of Lemma 2.4 are satis.ed for both copies. The corollary follows. As an immediate corollary of this result we show that for each g> 0 there are in.nitely many snarks with orientable genus precisely g. This result will also follow from Corollary 2.9. Corollary 2.6. For each g> 0 there exist in.nitely many snarks with ori­entable genus g. Proof. Wealreadyconstructedin.nitely many snarksembeddedinthetorus. For g> 1 we start with the snark J2g+1 which has orientable genus g. In the embedding described in the proof of theorem 2.1 edges c0d1 and c2d3 satisfyproperty P.ByLemma2.4 wehavein.nitely many snarks G0 = J2g+1, G1 = G0 · P , G2 = G1 · P , ..., embedded in Sg . There are two disjoint paths P1 connecting y1 and y2 and P2 connecting y3 and y4 in P -{u, v}. Therefore there is a subgraph in Gi+1 which is isomorphic to a subdivision of Gi. This implies that in Gi there is a subgraph which is a subdivision of J2g+1 and therefore Gi can not be embedded in a surface of genus less than g. 2.3 The genus of Pn In Corollary 2.5 we have described products P n which are embeddable in the torus. Inthis sectionwedescribeproducts P n which havegenus g,1 . g . n. We need the following lemma for the construction. Lemma 2.7. 1. If two adjacent vertices u and v are removed from the Petersen graph P then in a drawing of P -{u, v} in the plane, the degree 2 vertices can not be drawn on the boundary of the same face. 2. If we remove two edges e, f as indicated in Figure 2.8 from the Petersen graph, then the graph P -{e, f}is not planar. 3. For any vertex x . V (P )the graph P -{x}is not planar. Proof. For the .rst part note that if we have an embedding of P -{u, v}in the plane such that the degree two vertices are on the boundary of one face, then we can add a vertexin thatface and connectit to thedegree two vertices. 2.3 The genus of P n We get an embedding of the P/uv in the plane, which is a contradiction since P and P/uv are not planar graphs. For the second and third part note that in graphs P -{e, f}and P -{x} there are subdivisions of the graph K3,3 which implies they are not planar. Theorem 2.8. For each genus n . 1, there exists a dot product P n of n copies of the Petersen graph, whose genus is equal to n. Proof. We construct products P n together with their embeddings .n with the following properties. • The genus of P n is g(P n)= g(.n)= n • In the embedding.n there are two edges e, f . E(P n)onthe samefacial walk F such that thegenus of thegraph P -{e, f}is g(P n -{e, f})= n. Further there are two distinctfacial walks F1 and F2, both distinctfrom F, such that F1 contains e and F2 contains f (or equivalently there is exactly one facial cycles F which contains both e and f). For n = 1 we have g(P )= 1 and edges e, f from Lemma 2.7(See Figure 2.8) satisfy the stated conditions. Let u, v be adjacent vertices in P and denote the neighbors of v distinct from u with v1 and v2 and the neighors of u distinct from v with u1 and u2. Now supposewehaveanembedding.n of Pn, edges e = x1x2 and f = y1y2 and a facial walk F with required properties. We can assume that vertices x1,x2,y1,y2 appear in this order along the walk F. Denote the walks which contain edges e and f by F = x1x2P1y1y1P2x1, F1 = x2x1R1x2 and F2 = n y2y1R2y2. We construct P n+1 by removing edges e, f from P and vertices u, v from P and adding product edges e1 = x1v1,e2 = x2v2,f1 = y1u1,f2y2v2. We claim that g(P n+1)= g(P n+1 -{e1,e2})= n +1. nn+1) Since P -{e, f}has genus n it follows that g(P . n. Suppose that n+1)n g(P = n. Since the embedding of P -{e, f}induced by the embedding of P n+1 has genus n it follows that the embedding of P n+1 also induced an embedding of P -{u, v}into the plane so that the degree two vertices are on the same face. But this is a contradiction to Lemma 2.7. Now suppose that g(P n+1 -{e1,e2})= n. Again, since the induced em­bedding of P n -{e, f}hasgenus n, the induced embedding of P -{u, v}is in the plane such that two vertices u1,u2 are on the same face. But this would induce an embedding of P -{v}in the plane, a contradition to Lemma 2.7. We have shown that g(P n+1). n +1. Let P -{u, v} be embedded into the cylinder Z as shown on the Figure 2.9. In the embedding .n remove a discfrom theface F andjoin Sn with the cylinder Z using a sphere with three discs removed to obtain a surface Sn+1.We can addproduct edges on Sn+1 to obtain an embedding .n+1 into Sn+1 (see Figure 2.10). Facial cycles containing product edges are x2P1y1u112v2x2, y2P2x1v13u2y2 and x1R1x2v24u1y1R2y2u221v1x1 so the embedding .n+1 satis.es all require­ 2.4 Genus of the dot product ments. Corollary 2.9. For each g, 1 . g . n there exists a product P n with ori­entable genus g(P n)= g. Proof. Suppose 1 . g . n. By Theorem 2.8 we can construct a product P g with orientable genus g(P g)= g. By construction there is an embedding of P g into Sg such that allproductedgesareonthe sameface. Thisimpliesthat there are two edges e and f which satisfy property P of Lemma 2.4. From P g we can then construct a product P n with orientable genus g(P n)= g by successively applying Lemma 2.4. 2.4 Genus of the dot product In this section we give general bounds for the genus of the dot product. Theorem 2.10. Let G1 and G2 be two cubic graphs with orientable genera g(G1)= g1 and g(G2)= g2. Then thegenus of thedotproduct G1 · G2 satis.es g1 + g2 -2 . g(G1 · G2). g1 + g2 +1. The bounds are best possible, even if G1 and G2 are required to be snarks. Proof. Firstwe showtheupperbound. Let G1 beembeddedintothe surface S1 of genus g1 and G2 into the surface S2 of genus g2. Suppose that in the construction ofthedotproduct we remove edges e = x1x2 fromG1 and vertices u and v with neighbors {u1,u2,v}and {v1,v2,u}respectivelyfrom G2. Remove a small disc D around the edge uv in S2 which intersects G2 only in vertices u1,u2,v1,v2. Note that the vertices appear in this order around the disc D. Remove two discs D1 and D2 from S1 around edges e and f which intersect G1 only in end vertices of edges e and f. Nowjointhe surfaces S1 and S1 by a sphere with three discs removed. It is possible to add the product edges on the surface to get an embedding of G1 and G2 (see Figure 2.11). For the lower bound let G = G1 · G2 be embedded into a surface Sg of genus g. The product edges form a cut in G hence in the dual G* of G in Sg the edges corresponding to product edges in G form a union of cycles(we consider a loop to be a cycle of length 1). If we cut the surface Sg along these cycles, the surface is split into two surfaces S1 ' and S2 ' without some discs so that G1 -{e, f}is embeddedinto S1 ' and G2-{u, v}is embeddedinto S2' . We can assume that the vertices of degree 2 in G1 and G2 are on the boundaries of S1 ' and S2' . We do a case analysis on the number of cycles in G* (discs on the boundary of S1 ' and S2' ) corresponding to the cut formed by the product edges. Denote the set of these cycles by C. Suppose .rst that the boundary of S1 ' is a cycle C and that the boundary of S2 ' is a cycle D. Further assume that the vertices x1,x2,y1,y2 appear in this order along C and vertices u1,u2,v1,v2 appear in this order along D. Then we can adddiscsto S1 ' and S2 ' toget surfaces S1 and S2 sothat g(S1)+g(S2)= g(S) and we can also add edges e, f to obtain embeddings of G1 into S1 and vertices u, v to S2 to obtain and embedding of G2 into S2. Therefore g(G1)+g(G2). g(G)in this case. Assume that the order around C is x1y1x2y2 and that the order around D is v1u1v2u2. Nowwecandiscswithhandlesto S1 ' and S2 ' to obtain embeddings of G ' and G ' into S1 and S1. We can add edges e, g to G ' and vertices u, v 12 1 2.4 Genus of the dot product to S2 to get embeddings of G1 and G2 into S1 and S2. Therefore in this case g(G1)+g(G2)-2 . g(G). Because of symmetry these are allpossible casesif we have one cycle in C. Suppose we have two cycles in C. Surfaces S1 ' and S2 ' have boundaries consisting of cycles C1, C2 and D1, D2 respectively. There arethreepossibilities forpositions of vertices x1,x2,x3,x4 (x1,x2,x3,x4)around C1 and C2 (D1 and D2). Assume that vertices x1 and x2 are on the cycle C1 and y1 and y2 are on the cycle C2. Then we can add two discs to S1 ' toget a surface S1 andproduct edges to get an embedding of G1 into S1. We can add a handle to S2 ' toget a surface S2 and vertices u, v to S2 to get an embedding of G2 into S2. In this case we have g(S1)+g(S2)-1= g(S)-1 and hence g(G1)+g(G2). g(G). Assume that vertices x1 and y1 are on the cycle C1 and x2 and y2 are on the cycle C2. In this case we can add a handle to S1 ' and a handle to S2 ' to get surfaces S1 and S2 and add product edges to S1 and vertices u, v to S2 to get embeddings of G1 and G2 into S1 and S2. in this case we have g(S1)+g(S2)-2= g(S)-1 and hence g(G1)+g(G2)-1 . g(G). Thelastpossible caseisthatthereis a vertexx1 on C1 and vertices x1,y1,y2 on C2. Inthis case we againgetg(G1)+g(G2)-1 . g(G). Because ofsymmetry these are all possible cases when there are two cycles in C. Suppose that there are three cycles in C. There are cycles C1,C2,C3 on the boundary of S1 ' and cycles D1,D2,D3 on the boundary of S2' . Up to symmetry there are two possibilities for arrangement of vertices x1,x2,y1,y2 around C1,C2 and C3. First case is when vertices x1 and x2 are on C1 and y1 and y2 are on C2 and C3. The second case is when vertices x1 and y1 are on C1 and vertices x2 and y2 are on C2 and C3. In both cases we can add a sphere minus three discs to surfaces S1 ' and S2 ' to get surfaces S1 and S2 in which we can embed graphs G1 and G2. Therefore in this cases we have g(S1)+g(S2)+4= g(S)-2 and hence g(G1)+g(G2)-2 . g(G). The last possible case is that C consists of four cycles. In this case the boundares of S1 ' consist of four cycles each containing one of the vertices x1,x2,y1,y4. In this case we can add two handles to S1 ' toget a surface S1 and aspherewithfourdiscsremoved togeta surface S2 so thatgraphs G1 and G2 embed into S1 and S2. In this case we have g(S1)+g(S2)-5= g(S)-3 and hence g(G1)+g(G2)-2 . g(G). We only give a sketch of the proof that the bounds are best possible. Let C be a cycle in a graph G.A relative C-component of G is either an edge in E(G)\ E(C) with end points on C or a connected component of G - C together with all edges between G -C and C with their endpoints. An edge between a relative component of C and C is called a foot. A sequence of cycles C1,C2,...,Ck is planarly nested if for each Ci there exist relative components Hi of Ci such that H1 . H2 . ··· . Ck and that graphs obtained from G by contracting each edge of Hi except its feet are planar. We use the following theorem from[15]. Theorem 2.11(Mohar). If.is an orientable embeddingof G into a surface S of minimum genus g and C1,C2,...,Ck, k>g is a sequence of planarly nested cycles then cycles C1,C2,...,Ck-g bound discs in S. By using superposition we can construct a snarks G1 and G2 with an em­bedding of minimum genus g such that they contain planarly nested cycles C1,...,Ck (withrelative components H1,...,Hk)and D1,...,Dk (withrela­tive components H1' ,...,H k ' which are contained in subgraphs corresponding to supervertices of G1 and G2. Further we can add edges e and f a face in the relative component H1 such that relative components H1,...,Hk are no longerplanarand similarly adjacent vertices u and v connected tofour vertices ' '' of afacein H such that components H ,...,H Denote obtained graphs by 11k. G ' 1 and G ' 2. Since we only changed parts of G1 and G2 corresponding to su­pervertices, graphs G ' 1 and G ' 2 are snarks. From Theorem 2.11 it follows that g(G ' 1)= g(G ' 2)= g +1. If we construct the dot product by using edges e and f and vertices u and v weget a snark G ' · G ' with genus g(G ' · G ' )=2g and 12 12 so g(G ' 1)+g(G ' 2)-2= g(G ' 1 · G2' ). Using a similar idea we show that the upper bound is tight. Chapter 3 Polyhedral embeddings of snarks In this chapter we look at polyhedral embeddings of cubic graphs. We .rst prove that short cycles in polyhedral embeddings must be facial cycles. Us­ing this fact we show that Goldberg snarks and Szekeres snark do not have polyhedral embeddings into orientable surfaces. Szekeres showed that .ower snarks do not have polyhedral embeddings into orientable surfaces. We give a simpler proof of this result which works also for graphs Jk where k is even. Wealsoshowthat.ower snarksdonothavepolyhedral embeddingsintonon­orientable surfaces. On the other hand we construct polyhedral embeddings of the Goldbers snarks into non-orientable surfaces. We prove that for each non-orientable surface N thereexist snarkswhichhavepolyhedral embedding into N. 3.1 Short cycles In this section we look at short cycles in polyhedral embeddings. Let G be a cubic graph with a short cycle C has a polyhedral embedding, then C is very likely to be a facial cycle. This is established by the following lemmas. Lemma 3.1. Let G be a cubicgraph and C a3-cycle of G. Then C is afacial cycle in every polyhedral embedding of G. Proof. Let C = v0v1v2v0 be a 3-cycle of G. Denote the neighbor of vi not in C with vi' , i =0, 1, 2. A facial cycle in a polyhedral embedding of G cannot contain any of the paths vi' vivi+1vi+2v ' =0, 1, 2, indices modulo 3, since i+2, i it must be induced. This implies that we have three facial cycles at C, which contain vi' vivi+1vi' +1, i =0, 1, 2, indices modulo 3. Then C is a facial cycle. 37 Lemma 3.2. Let G be a cubicgraph otherthan K4 and let C be a 4-cycle of G. Then C is a facial cycle in every polyhedral embedding of G. Proof. If G has apolyhedral embedding and G is not K4, then every 4-cycle of G is induced, since G is 3-connected by Proposition 1.6. Let C = v0v1v2v3v0 be a 4-cycle of G and let vi ' be the neighbor of vi not in C, i =0, 1, 2, 3. Suppose that all facial cycles, which intersect C, intersect C in one edge only. For each edge vivi+1 there is a facial cycle Ci which contains the path '' ' v where indices are modulo 4. Therefore all edges viv are contained ivivi+1vi+1 i twice and edges vivi+1 are contained once in facial cycles ci, i =0, 1, 2. There­fore C must be a facial cycle since edges vivi+1 must be covered twiceby facial cycles. Suppose thereis atleast onefacial cycle C1 .C whichintersects C in more = thanoneedge. Facial cyclesinpolyhedral embeddingsareinduced. Hencewe may assume that C1 contains the path v0' v0v1v2v2' . The other facial cycle C2, ' '' which contains the edge v0v0, must contain the path v in order not to 0v0v3v3 intersect C1 at v2. The third facial cycle through v0 then contains edges v0v1, v0v3 and v3v2, which is a contradiction. Let a graph G be embedded in a surface S, let F be a facial cycle and let C be a cycle of G. We say that F is k-forwarding at C, if F and C intersect precisely in k consecutive edges on C. Lemma 3.3. Let G be a cubic graph and C an induced 5-cycle of G. If G has a polyhedral embedding in a surface S, then the following holds. (a) If S is orientable, then C is a facial cycle. (b) If S is non-orientable, then either C is a facial cycle or all facial cycles that intersect C are 2-forwarding at C. Proof. Let C = v0v1v2v3v4v0 be a 5-cycle of G. Suppose that no facial cycle (other thanpossiblyC)intersects C in more than one consecutive edge on C. Then it is easy to see that C is a facial cycle. Now let F be a facial cycle that intersects C in at least two consecutive edges on C. Facial cycles in polyhedral embeddings are induced. Therefore F is either 3-forwarding or 2-forwarding at C. If F is 3-forwarding, we can assume that the path v0' v0v1v2v3v3 ' is in F . Thenthefacial cycle, which containsthepath v0v4v3, intersects twice with F . This contradiction implies that no facial cycle is 3-forwarding at C. 3.1 Short cycles We may assume that F contains the path v0' v0v1v2v2' . The facial cycle, which contains the path v1' v1v2, must contain the path v1' v1v2v3 so it is 2­forwarding. If we continue along the cycle C, we see that all facial cycles at C are 2-forwarding at C. To complete the proof, we will show that S is not orientable, if all facial cycles at C are 2-forwarding. Suppose that S is orientable and let Ci be the facial cycle, which containsthepath vivi+1vi+2, i =0, 1, 2, 3, 4, indices modulo 5. We can assume that in the orientation of C0, induced by the orientation of S, vertices v0v1v2 are in clockwise order. Then the vertices v3v2v1 are in this clockwise order on C1. If we continue along C,we seethatin C4 vertices v4v0v1 are in clockwise order. But then C0 and C4 induce the same orientation of the edge v0v1, which is a contradiction with the assumption that S is orientable. Corollary 3.4. Ifa cubicgraph G contains twoinduced5-cycles, whoseinter­sectionis nonempty andis notjust a common edge,then G has no orientable polyhedral embeddings. Proof. Suppose we have an orientable polyhedral embedding of G. By Lemma 3.3 both 5-cycles are facial. This is a contradiction with the fact that theirintersection contains morethanjust one edge. In the Petersen graph P every edge is contained in four induced 5-cycles. Lemma 3.3 therefore implies that P hasno orientablepolyhedral embeddings. However, P has apolyhedral embeddingintheprojectiveplane(seeFigure 3.1). Lemma 3.3 and its Corollary 3.4 can be applied on many other snarks, for example the Szekeres snark that is shown in Figure 3.2. Theorem 3.5(Szekeres). The Szekeres snark has no polyhedral embed-dings. Proof. Eachof the.ve “parts”of theSzekeres snark(seeFigure3.2) contains a path v1v2 ...v9 on 9 vertices and a vertex v0 that is adjacent with v2, v5, v8 andfurtherthere are edges v1v6 and v4v9. There arefourinduced5-cyclesC1 = v0v2v1v6v5v0, C2 = v0v2v3v4v5v0, C3 = v0v8v9v4v5v0 and C4 = v0v8v7v6v5v0. Cycles C1 and C2 intersect at two edges adjacent to v0. Therefore they are not both facial cycles. If none of C1, C2 is facial, then the 2-forwarding facial cycles at C1 and C2, which contain their intersection C1 .C2, are distinct and intersect in two edges. So one of them is facial and the other is not. Similarly, one of the cycles C3, C4 is facial and the other one is not. Suppose the cycle C2 isfacial. Then itis1-forwarding at C4, so C4 is facial and C1 and C3 are not facial. This implies that there is a facial cycle that contains the path v1v6v5v4v9 and another facial cycle that contains the path v1v2v0v8v9, which is a contradiction. Suppose now that C2 is not facial. Then C1 is facial and is 1-forwarding at C4. So C4 is a facial cycle and C3 is not. This implies that there is a facial cycle that contains the path v3v2v0v8v7 and another facial cycle that contains the path v3v4v5v6v7, which is a contradiction. Nonexistence of orientable polyhedral embeddings of the Szekeres snark hasbeenproved earlierby Szekeres[5]. 3.2 Small edge-cuts Let G1 and G2 be cubic graphs and v1 . V (G1), v2 . V (G2). Denote the three neighbours of v1 in G1 by z0,z1,z2 and the three neighbours of v2 in G2 by u0,u1,u2. Let G = G1 * G2 be the cubic graph obtained from graphs G1 and G2 by deleting vertices v1 and v2 and connecting vertices ui with zi for i =0, 1, 2. We call G the star product of G1 and G2. It is easy to see that the graphG is3-edge-colorableif and onlyifboth G1 and G2 are3-edge-colorable. Theorem 3.6. The starproduct G = G1 * G2 has apolyhedral embedding in an(orientable) surfaceif and only ifboth G1 and G2 have polyhedral embed­dingsin some(orientable) surfaces. 3.2 Small edge-cuts Proof. Suppose we have polyhedral embeddings of G1 and G2. At vertex v1 we have three facial cycles Ci = ziv1zi+1Pizi for i =0, 1, 2, indices modulo 3. At vertex v2 we have three facial cycles Di = uiRiui+1v2ui for i =0, 1, 2. Since the embeddings are polyhedral, paths P0, P1, P2 and paths R0, R1, R2 are pairwise disjoint. In the embedding of the star product G = G1 * G2 we keep all facial cycles from embeddings of G1 and G2, which do not contain vertices v1 and v2, and add three new facial cycles Fi = ziuiRiui+1zi+1Pizi, i =0, 1, 2, indices modulo 3. Facial cycles in G, which are facial cycles in G1 or G2, intersect pairwise at most once. A facial cycle F , which is also a facial cycle in G1 or G2, intersects the facial cycle Fi, i =0, 1, 2, only onthepath Pi or only on the path Ri. So it intersects Fi at most once. Facial cycles Fi and Fi+1 intersect only in the edge ui+1zi+1, i =0, 1, 2, indices modulo 3, since the paths P0,P1,P2 and R0,R1,R2 are pairwise disjoint. So the embedding of G is polyhedral. It is easy to see that the embedding of G is orientable if and only if the embeddings of G1 and G2 are orientable. Suppose now that G has a polyhedral embedding. The three edges ziui, i =0, 1, 2, form a 3-cut in G. Since the embedding is polyhedral, we have three facial cycles Fi = uiRiui+1zi+1Piziui, such that Fi and Fi+1 intersect in the edge zi+1ui+1, i =0, 1, 2, indices modulo 3. We may assume that there are no negative signatures on edges ziui, i =0, 1, 2. In the embedding of G1 (and G2) we keep all facial cycles, which do not intersect G2 (respectively GG1 G2 Figure 3.3: The star product G of graphs G1 and G2. G1), and add vertices v1, v2 with such local rotations that we obtain new facial cycles Ci = ziv1zi+1Pizi in G1 and Di = uiRiui+1v2ui in G2, i =0, 1, 2, induces modulo 3. Since we have no new intersections between facial cycles (intersections onziui become intersections on ziv1 and uiv2), the embeddings of G1 and G2 are polyhedral. It is also clear that both embeddings are in orientable surfacesif and onlyif theembedding of G isorientable, sincewedid not change local rotation at any vertex or change the signature of any edge. If the embedding of G = G1 * G2 in a surface S is constructed as in the proof of Theorem 3.6 from embeddings of G1 and G2 in surfaces S1 and S2 of Eulergenus o(S1)= k1 and o(S2)= k2, respectively,thentheEulergenus of S is o(S)= k1 +k2.Thisis easilyprovedby using Euler’sformulafor G, G1 and G2. Let G1 and G2 be cubic graphs. Choose an edge e = xy in G1 and two nonadjacent edges f1 = u0u1 and f2 = u2u3 in G2. Denote the neighbors of x in G1 by v0, v1, and the neighbors of y by v2, v3. Let G bethedotproduct of G1 and G2 obtained by deleting vertices x, y in G1 and edges f1, f2 in G2 and joining pairsviui, i =0, 1, 2, 3. Theorem 3.7. Let G1 and G2 be cubicgraphs. If G1 and G2 havepolyhedral embeddingsin(orientable) surfaces S1 and S2, such that the geometric dual of G2 is not a complete graph, then a dot product G = G1 · G2 exists, which hasapolyhedral embeddinginan(orientable) surface S. If the Euler genera of surfaces S1 and S2 are o(S1)= k1 and o(S2)= k2, then the Euler genus of 3.2 Small edge-cuts GG1 G2 Figure 3.4: The dot product G of graphs G1 and G2. S is o(S)= k1 + k2. Proof. Suppose that we havepolyhedral embeddings as described. We claim that G2 contains facial cycles D0, D1, D2, such that D1 intersects D0 and D2 but D0 and D2 donotintersect. To seethis,considerthedualgraph R. Since it is not a complete graph, it has two vertices c0 and c2 that are at distance two in R. If c1 is their common neighbor, then we can take D0, D1, D2 to be the facial cycles corresponding to c0, c1 and c2, respectively. Let f1 = u0u1 and f2 = u2u3 be the intersections between D0, D1 and D1, D2, respectively, and choose an arbitrary edge e = xy in G1. Denote the neighbors of x and y in G1 so that the facial cycles, which contain x or y, are C0 = v0xv1P0v0, C1 = v1xyv2P1v1, C2 = v2yv3P2v2, and C3 = v3yxv0P3v3. Since the embedding of G1 is polyhedral, paths P0, P1, P2, P3 are pairwise disjoint, except that P0 and P2 may intersect. In G2 we will use the following notation for facial cycles: D0 = u0R0u1u0, D1 = u0u1R1u2u3R3u0 and D2 = u2R2u3u2. The paths R0, R1, R2, R3 are pairwise disjoint. In the embedding of G wekeep alllocal rotations at vertices of G1 and G2, which are notdeleted (withadded edges naturally replacing deleted edges), and all edge signatures. Instead of facial cycles Ci, Di we get a facial cycle Fi = viuiRiui+1vi+1Pivi, i =0, 1, 2, 3, indices modulo 4. Since the paths Pi, Ri are pairwise disjoint, exceptforthepossibleintersectionbetween P0 and P2, allintersectionsbetween facial cycles Fi, i =0, 1, 2, 3, are the intersections of Fi and Fi+1 in edges vi+1ui+1, i =0, 1, 2, 3, indices modulo 4, and possibly one more intersection between F0 and F2. It is clear that any facial cycle F that does not contain any of the vertices vi, ui intersects at most once with any Fi and that two such facial cycles intersect at most once. So the embedding of G ispolyhedral. Itis also clear that if the embeddings of G1 and G2 are in orientable surfaces, the embedding of G is also in an orientable surface. The Euler genus of S is obtained from Euler’s formula and equalities |V (G)| = |V (G1)|+ |V (G2)|-2 |E(G)| = |E(G1)|+ |E(G2)|-3 |F (G)| = |F (G1)|+ |F (G2)|-3 from which we conclude that o(S)= k1 + k2. Theorem 3.8. Let G be a cubic graph and S a minimal cyclic 4-cut in G. If G admits a polyhedral embedding (in an orientable surface), then there exist graphs G1 and G2, such that G = G1 · G2 and G1 admits a polyhedral embedding(in an orientable surface). Proof. Suppose that the edges uivi, i =0, 1, 2, 3, form a 4-cut S in G. If a facial cycle contains more than two edges of S, the embedding of G can not be polyhedral. So we have four distinct facial cycles F0, F1, F2, F3 that contain edges of S. Since S is a cut, every cycle Fi, i =0, 1, 2, 3, contains two edges of S. Since the embedding is polyhedral, each of the Fi intersects two other Fj , Fk. In the dual a subgraph induced by the vertices corresponding to Fi, i =0, 1, 2, 3, is a simple graph on four vertices in which all vertices are of degree 2. It must be a 4-cycle. Therefore we can assume that faces Fi and Fi+1 intersect in the edge vi+1ui+1, i =0, 1, 2, 3, indices modulo 4. Each facial cycle Fi is then of the form Fi = viuiRiui+1vi+1Pivi. Since F0 and F2 intersect at most once, we can assume theydo notintersect at thepaths P0 and P2. Let G1 be the component of G -S, which contains paths Pi. If we set rotations of all vertices in G2 as they are in G (andreplace deleted edges naturally with added edges), we can set rotations around vertices x and y so that the facial cycles in G1, which do not contain x or y, remain unchanged and we have four new facial cycles C0 = v0xv1P0v0, C1 = v1xyv2P1v1, C2 = v2yv3P2v2, and C3 = v3yxv0P3v3. Since we added no new intersections between facial cycles, which were already in G, and facial cycles Ci, i =0, 1, 2, 3 intersect pairwise only once, the embedding of G1 is polyhedral. If the embedding of G is in an orientable surface, it is clear that the embedding of G1 is in an orientable surface. 3.2 Small edge-cuts Suppose wehavepolyhedralembeddings of cubicgraphs G1 and G2, atleast one of which is in a non-orientable surface. Let us construct the embedding of the dotproduct G = G1 · G2 asintheproof ofTheorem3.7. If the embedding of G is in orientable surface, then we may assume that all signatures of edges are positive. Now we can construct embeddings of G1 and G2 similarly as the embedding of G1 in the proof of Theorem 3.8, which are both in orientable surfaces and have the same set of facial cycles as the embeddings of G1 and G2 with which we started. Since at least one of these two is an embedding in a non-orientable surface, we have a contradiction. This shows Corollary 3.9. Ifwehavepolyhedral embeddings of G1 and G2, atleast one of whichisnon-orientable, and construct apolyhedral embedding of G = G1 · G2 as in the proof of Theorem 3.7, then the embedding of G is non-orientable. Let G1 and G2 be cubic graphs. Choose a vertex v in G1, an edge v3v4 in G1 and a vertex z0 in G2. Let the three neighbors of v be v0,v1,v2 and let z1,z2,u4 be the neighbors of z0. Let the neighbors of z1,z2 other than u be u0,u1 and u2,u3, respectively. If all these vertices are distinct, remove the vertex v from G1, vertices z0, z1, z2 from G2 and the edge v3v4 from G1. If wejoin pairs viui, i =0, 1, 2, 3, 4, we get a cubic graph G = G1¦G2, which is called a square product of graphs G1 and G2 (see also Figure 3.5). The cut Q = {viui |i =0,..., 4} in G is said to be the product cut. It is claimed in [19]that if G1 and G2 are snarks, then G is also a snark, however this is not trueingeneral. Forresultsconcerning 5-cutsin snarks, see[13]. Theorem 3.10. Let G be a cubic graph with a matching Q, which is a 5­cut of G. If G admitsapolyhedral embedding(inanorientable surface),then there existgraphs G1 and G2 suchthat G = G1¦G2 and Q isthe corresponding productcut and such that G2 admits apolyhedral embedding(in an orientable surface). Proof. Suppose that G has a polyhedral embedding. Since Q is a cut, every facial cycle contains an even number of edges in Q. It is easy to see that none of them contains four edges of Q (since the embedding is polyhedral). This implies that there are precisely 5 facial cycles F0,...,F4 that intersect Q and that the edges viui of Q, i =0,..., 4, can be enumerated so that Fi contains edges viui and vi+1ui+1, indices modulo 5, and v0,...,v4 are in the same component of G - Q. The facial cycles Fi are of the form Fi = viuiRiui+1vi+1Pivi, i =0,..., 4, indices modulo 5. Since the embedding is polyhedral, every one of the pairs of paths Pi, Pi+1 and Ri, Ri+1 is disjoint. Suppose that the facial cycles Fi and Fi+2 are disjoint for some i. Then both pairs Pi, Pi+2 and Ri, Ri+2 are disjoint. One of the pairs Pi+2, Pi+4 and GG1 G2 Figure 3.5: The square product of G1 and G2. Ri+2, Ri+4, i =0,..., 4, is disjoint. Because of the symmetry, we can assume that the pair Ri+2, Ri+4 is disjoint. Suppose now that all pairs of cycles Fi,Fi+2, i =0,..., 4, intersect. In at least three out of .ve pairs, Fi and Fi+2 intersectonthe same “side” (Pi and Pi+2 or Ri and Ri+2). By symmetry, we may assume that intersections are between Pi and Pi+2. Since facial cycles Fi and Fi+2 intersect at most once, it follows that there exists an index j such that Rj , Rj+2, Rj+4 are pairwise disjoint. By above, we can assume that R4, R1, R3 are pairwise disjoint. Now we can add to G - Q new vertices v, z0, z1, z2 and edges v0v, v1v, v2v, v3v4 and u0z1, u1z1, u2z2 ,u3z2, z1z0, z2z0, u4z0 so that the graph G is a square product of G1 and G2. In the embedding of G2 we keep all rotations and signatures of vertices and edgesthat were alreadyin G and we naturally replace deleted edges with the added ones. Around vertices z0, z1, z2 we can set rotations so that facial cycles in G2, which were not already in G, are D0 = u0R0u1z1, D1 = z0z1u1R1u2z2z0, D2 = z2u2R2u3z2, D3 = z0z2u3R3u4z0 and D4 = z0u4R4u0z1z0. The only new intersections of facial cycles of G2 are between D4 and D1 and between D1 and D3. Hence the embedding of G2 is polyhedral and if the embedding of G is in an orientable surface, so is the 3.3 Flower snarks embedding of G2. 3.3 Flower snarks In this section we prove that Flower snarks J2k+1 do not have polyhedral em-beddings. This was .rst proved by Szekeres using polyhedral decompositions. Hisproof only workedforgraphs J2k+1 but not forgraphs J2k and onlyfor ori­entable embeddings. We give a simpler proof which also works for all graphs Jk and also for non-orientable embedding. The goal for this section is to prove the following theorem. Theorem 3.11. Fork . 4the .owergraph Jk has nopolyhedralembeddings. We .rst prove the theorem for larger k and then prove the theorem for smaller values of k. Note that the graph J3 is obtained from the Petersen graph P by replacing one vertex in P by a triangle. Since Petersen graph has a polyhedral embedding into the projective plane so does J3. Since there are nopolyhedral embeddings of P into orientable surfaces it follows from the Lemma 3.1 that J3 has no polyhedral embeddings. Suppose that we have a polyhedral embedding of Jk. Let us look at how facial cycles can traverse Yj . If we walk along afacial cycle C, come to Yj from Yj-1 and then leave Yj going back to the tile Yj-1, we say that C is a backward face at Yj . Similarly we de.ne a forward face at j, which is a facial cycle that enters Yj from Yj+1 and leaves it towards Yj+1. If a cubic graph G has a polyhedral embedding, then at every vertex v . V (G)with neighbours v1,v2,v3, each path P = vivvj , j .= i, de.nes a unique facial cycle, which we will denote by F (P ). Lemma 3.12. If C is a facial cycle that contains at least two vertices of Yj , then the intersection of C with Yj is one of the three possible paths: aj bj cj , aj bj dj or cj bj dj . Proof. A cycle C can enter and exit Yj only through vertices aj , cj or dj . Suppose now that aj ,cj . V (C). The facial cycle C ' = F (aj bj cj ) intersects C in two nonadjacent vertices aj and cj , so C = C ' and C ' contains the path aj bj cj . Similar conclusion holds if aj and dj are on C or if cj and dj are on C. Since all facial cycles are induced, the intersection C .Yj can consists only of one of the three paths. Afacial cycle, whichis neitherforward norbackward at Yj ,is called a cross face. It follows from Lemma 3.12 that each facial cycle, which intersects Yj , is either a backward, forward or a cross face. Lemma 3.13. At Yj there canbe at most onebackward(forward) face. If thereis onebackwardface, then thereis also oneforwardface andfourdistinct cross faces. The backward face at Yj is forward at Yj-1 and the forward face at Yj is backward at Yj+1. Proof. Suppose we have two backward (forward) faces. By Lemma 3.12 they intersect at an edge adjacent to bj . If they intersect at bj aj , they also intersect at aj-1aj , whichis a contradiction. Similarly weget a contradiction, if theyintersect at bj cj or bj dj .This showsthatthereisat mostonebackward (forward)face. Suppose now that C is abackwardface. The edgesbetweenYj and Yj+1 are traversed twice by C and four times by cross faces. The cross faces therefore traverse the edges between Yj and Yj+1 at most four times, hence there must be a forward face at Yj . IfC containsthepath aj bj cj , then {aj-1,dj-1}.C.Yj-1. ByLemma3.12, C .Yj-1 = aj-1bj-1dj-1, so C is a forward face at Yj-1. A similar conclusion 3.3 Flower snarks holds if C .Yj is either aj bj dj or cj bj dj . Similarly we also show that a forward face at Yj is backward at Yj+1. Out of facial cycles F (aj bj cj ), F (aj bj dj ) and F (cibj dj ) one is a backward face, one is a forward face and one is a cross face. Since the one that is a cross face is the only cross face, which contains more than one vertex of Yj , all cross faces are distinct. A backward face at j is called a bottom face if it contains the edge aj-1aj and is called a top face if it does not contain aj-1aj . A top face at Yj is of the form cj-1bj-1dj-1cj bj dj cj-1. So it is clear that we cannot have backward top faces at Yj and Yj+1 at the same time. The tile Yj is of type 0,if allfacial cycles, whichintersectit, are crossfaces. Itis of type 1, if there is one forward and one backward face at Yj . Lemma 3.12 implies that if thegraph Jk has apolyhedral embedding, then all tiles are of type 0 or all tiles are of type 1. Lemma 3.14. If Jk has a polyhedral embedding, then k . 6 and all tiles are of type 1. Proof. By Lemma 3.12 every polyhedral embedding of Jk has at least four crossfaces. For each j =0,...,k -1 wehave atleast oneintersectionbetween four selected cross faces on edges from Yj to Yj+1. Since we can have at most 6 such intersections, we have k . 6. If all tiles are of type0, then Jk hasprecisely6facial cycles. Thegeometric dual of G on S has 6 vertices and 4k2 ·3 =6k edges. Since the dual is a simple graph, it has at most 15 edges, so 6k . 15. This implies that k . 2. Lemma 3.15. The graph J4 has no polyhedral embeddings. Proof. Suppose we have a polyhedral embedding of J4. All tiles are of type 1, sothereareprecisely4 crossfaces. Wehavethree4-cycles C1 = a0a1a2a3a0, C2 = d0c1d2c3d0, C3 = c0d1c2c3c0 in J4, which are facial cycles by Lemma 3.2. These cycles are all cross faces. As in the proof of Lemma 3.14, we see that there are at least four intersections of cross faces. But since C1, C2, C3 are pairwise disjoint, this is not possible. Lemma 3.16. The .ower snark J5 has no polyhedral embeddings. Proof. Suppose we have a polyhedral embedding of J5. Each tile must be of type 1. If all backward faces are bottom faces, then the inner cross face a0a1a2a3a4a0 does not intersect any other cross faces. So we have 5 intersec­tions between three cross faces, which is not possible. Since we cannot have two consecutive top faces, we must have two consec­utive bottom faces at tiles j and j +1 and a top face at tile j +2. We can assume j = 1. The facial cycle F (a0a1a2) contains the path a0a1a2a3a4. If not, it would intersect twice with one of the bottom faces at tiles 1 or 2. So it must be a0 ...a4a0. The facial cycle, which contains b2a2 and is di.erent from the backward face at tile 2, must contain the path b2a2a3b3. This facial cycle intersects twice with the facial cycle d2b2c2d3b3c3d2, which is a contradiction. Lemma 3.17. The graph J6 has no polyhedral embeddings. Proof. All tilesin J6 are of type1. Wehave three6-cycles C1 = a0a1 ...a5a0, C2 = c0d1c2 ...d5c0 and C3 = c0d1c2 ...d5c0. From previous proofs it follows that at each tile Yj one of the four cross faces goes from one of C1, C2, C3 to another. We say that this cross face has made a transition at Yj . It is obvious that if a cross face makes at least one transition, it makes more than one transition. So one cross face makes no transitions, since we can have at most 6 transitions. Let the four cross faces be F1, F2, F3, F4 and let F1 be the one, which does not make any transition. Because of the symmetry, we can assume that F1 = C1. Therearefourcrossfacesand sixintersectionsbetweenthem. Thisimplies that they must all pairwise intersect and in particular, all cycles F2, F3, F4 intersect F1. All transitions of cross faces are transitions of Fi to C1 and from C1, i =2, 3, 4. In particular, the cycle F2 makes a transition to the cycle C1 at some tile Yj and a transitions from C1 at the tile Yi+1. But then F2 is not induced, which is a contradiction. This completes the proof of Theorem 3.11. 3.4 Goldberg snarks We now look at polyhedral embeddings of Goldberg snarks. We show that Goldberg snarks do not have polyhedral embeddings into orientable surfaces but they do have polyhedral embeddings into non-orientable surfaces. Theorem 3.18. No Goldberg graph has a polyhedral embedding in an ori­entable surface. On the other hand, every Goldberg graph Gk, k . 3, has a polyhedral embedding in the non-orientable surface of Euler genus k. 3.4 Goldberg snarks Proof. Suppose that the graph Gk has a polyhedral embedding in an ori­entable surface. For every i =0,...,k - 1 we have have two 5-cycles Bi = bidihigicibi and Ci = bidifieicibi. By Lemma 3.3 both are facial cycles. This is a contradiction, since Bi and Ci intersect in two edges cibi and bidi. An embedding in a non-orientable surface has the following facial cycles: (a) A = a0a1 ...ak-1a0 and B = f0e0f1e1 ...fk-1ek-1f0, (b) Ci = bidifieicibi, i =0,...,k -1, (c) Di = gihigi+1hi+1di+1fi+1eicigi, i =0,...,k -1, (d) Ei = aiai+1bi+1ci+1gi+1hidibiai, i =0,...,k -1. It is easy to see that this determines a non-orientable polyhedral embedding. TheEulergenusof theunderlying surfaceof theembeddingiscalculatedfrom Euler’sformula2-o(Gk)= |V (Gk)|-|E(Gk)|+|F (Gk)|=8k -23 8k +3k +2 = 2-k. Goldberggraphshave morethan onepolyhedral embedding, not all of the same genus. They can be described as follows. Consider the subgraph Ti induced on vertices ai, bi, ci, di, ei, fi, gi and hi. Let uslook athowfacial cycles can traverseit. There are(atleast) two possibilities. There is a facial 5-cycle Ci = bidihigicibi and there are facial cycles that contain paths P1 i = ai-1aiai+1, P2 i = gi-1higihi+1, P3 i = gi-1hidifieifi-1, P4 i = hi+1gicidieifiei+1, P5 i = ei+1fidibiaiai+1 and P6 i = fi-1eicibiaiai-1, where P1 i and P2 i canpossibly bepart of the samefacial cycle. In such case,we say that Ti is of type 1. The second possibility is the following. There is a facial 5-cycle Di = bicieifidibi and there arefacial cycles that containpaths R1 i = ai-1aiai+1, R2 i = fi-1eifiei+1, R3 i = ai-1aibidihigi-1, R4 i = ai+1aibicigihi+1, R5 i = fi-1eicigihigi-1 and R6 i = ei+1fidibihigihi+1, where R1 i and R2 i canpossiblybepart of the same facial cycle. We say that Ti is of type 2. We now choose arbitrary the types of all subgraphs Ti andjoinfacial seg­ments described above into facial cycles as follows. There is an automorphism of the graph Gk, which sends all cycles Ci into cycles Di, so we can assume that the subgraph Ti isof type1. If not,wejoinfacial segmentssymmetrically according to this automorphism. If subgraphs Ti and Ti+1 areboth of type1,wejoinfacial segments P1 i and P i+1 , P i and P i+1 , P i and P i+1 and facial segments P i and P i+1 . 12243 56 3.4 Goldberg snarks If the subgraph Ti is of type 1 and Ti+1 oftype2,wejoinfacial segments 1,Ri+1 P i and P i, facial segments Ri+1 , P i and Ri+1 and facial segments P i and 32152 4 Ri+1 . If all subgraphs Ti are of type1(or all are of type2),thenthe embedding is the one described in theproof of Theorem 3.18. If there are two consecutive subgraphs Ti and Ti+1 ofdi.erenttypes,we saythatthereisa transition at i. It iseasyto seethattheembeddingispolyhedralif wehaveatleast6 transitions. It is also easy to see that the number of facial cycles of the embedding is 3k. In this manner we have obtained a large number of(combinatorially)di.erent polyhedral embeddings of the graph Gk in a surface of Euler genus k +2. ThisshowsthatGoldberg snarksadmitpolyhedral embeddingsindistinct non-orientable surfaces (of Euler genera k and k + 2) and that they admit combinatorially di.erent polyhedral embeddings in the same non-orientable surface(of Euler genus k +2). Corollary 3.19. For every positive integer k there exists a snark which has a polyhedral embedding into Nk. Proof. ThePetersengraphP has apolyhedralembeddingin N1. ByTheorem 3.18 the Goldberg snark G2k+1 hasapolyhedral embedding in N2k+1 for every k . 1. The graph G3 is not a snark since it contains a 3-cycle C = a0a1a2a0. If we contract C to a vertex, we obtain a snark G ' 3, whichpolyhedrally embeds in N3 (cf. Theorem 3.6). For k> 1 we have a snark H2k+2 = G2k+1 · P , which polyhedrally embeds in N2k+2, and H4 = G ' 3 · P , which polyhedrally embeds in N4 (cf. Theorem 3.7). The dotproduct H2 = P · J3 polyhedrally embeds in N2. The graph H2 is not 3-edge-colorable, but is not a snark, since the girth of H2 is 4. There are two non-isomorphic dot products of two copies of the Petersen graph P , but since the dual of P in the projective plane is K6, we cannot use Theorem 3.7 to obtain a snark with polyhedral embedding into the Klein bottle. Indeed, it can be shown that they do not have such embeddings. We construct a superposition G28 of the Petersen graph in the projective plane to get a snark embedded in the Klein bottle. Take an edge e = uv in thePetersengraph. Replace vertices u and v with(1,1,3)-supervertices in the Figure4.6and the edge e with the superedgeobtainedfromthePetersengraph by removing vertices x and y (see Figure 3.8). We claim that we get a snark withpolyhedral embedding intotheKleinbottle(seeFigure3.9). G28 is clearly a snark since it was constructed as a superposition of the Petersen graph. In the embedding in Figure 3.9, facial cycles which cross cross-caps do not contain bad edges since these cycles come from embeddings of thePetersengraphintotheprojectiveplane. Itisalsoclearfromthe .gure that other cycles do not contain bad edges. Chapter 4 The defect of a graph In this part of the thesis we de.ne the defect of a graph which is a measure for how far a graph is from having a polyhedral embedding. The defect is de.ned so that for a given graph it is easy to compute. Using a computer and a database of snarks with up to 28 vertices we show that the Gr¨unbaum conjecture is true for all snarks with up to 28 vertices. Using the defect we show that the Gr¨unbaum conjecture is true for Kochol snarks. The family of Kochol snarks is a rich family of snarks which includes for instance snarks with arbitrarily large girth. We then prove some theoretical results about the defect. In particular we show that if Gr¨unbaum conjecture is true than the defect for any snark is at least two, and for any k . 2 we construct an in.nite family of snarks with defect precisely k. We showthattheGr¨unbaumconjectureimpliesa stronginequalitybetween thedefect and resistanceof snarks. Resistanceisameasureforhowfara snark isfromhaving 3-edge-coloring. Weprovethatif theGr¨unbaum conjectrureis true, graphs with high resistance have high defect. 4.1 De.nition of defect and computer search We de.ne the defect of agraph as a measureforhowfar a(cubic) graphis fromhaving apolyhedral embedding. Let.be an embedding of a cubicgraph G and let F = {W1,...,Wk}be the collection of facial walks of .. For a walk Wi .F we de.ne the defect d(Wi) of Wi to be the number of edges which appear twice along Wi. For two facial walks Wi,Wj .F, i .= j, we de.ne the defect d(Wi,Wj )as 0; |E(Wi).E(Wj )|=0 d(Wi,Wj )= |E(Wi).E(Wj )|-1; |E(Wi).E(Wj )|> 0. 55 The defect of the embedding . is de.ned as k d(.)= d(Wi)+ d(Wi,Wj ). i=1 1.i 0 for every snark G. Stated with resistance, the Gr¨unbaum conjecture is equivalent to the statement that for every graph G, d ' (G) > 0 if r(G) > 0. The following theorem gives a stronger implication. Theorem 4.7. The following statements are equivalent: 1. the Gr¨unbaum conjecture is true, 2. for all snarks G we have d ' (G). r(2 G) . Proof. It is clear that 2 implies 1. We show that 1 implies 2. Suppose 2 is false. We have a we have a snark G which has a polyhedral embedding into an orientable surface with defect 2d ' (G) 0 for i 2k. Now the inequality r(Gi). r(Gi-1)-2impliesr(Gk)> 0. SoGk isa snarkwhichhasapolyhedral embedding and is therefore a counter-example for the Gru¨unbaum conjecture. Suppose we have an embedding of Gi. We replace a bad edge e =(xy) in the embedding of Gi with a graph on 10 vertices to get a graph Gi+1 with an induced embedding of smaller modi.ed defect (see Figure 4.7). In the embedding of Gi we can assume we have facial walks W1, W2, W3, W4 which contain paths x1xyy1, y1yy2, y2yxx2 and x2xx1 respectively, where some of W1, W2, W3, W4 may be equal. To de.ne an embedding of Gi+1 we take facial walks of the embedding of Gi, replace paths x1xyy1, y1yy2, y2yxx2 and x2xx1 on walks W1, W2, W3, W4 with paths x1654y1, y1432y2, y2210x2 and x2076x1 and add facial cycles 01870, 123981, 34593 and 567895. By appropriately choosing the bad edge e we can guarantee that the modi.ed defect decreases by at least one. We distinguish 4 choices for the bad edge e. At each step we can make choice3 onlyif we can not make choices1 or2 and can make choice4if we can not make choices 1, 2, or 3. As long as the defect of the embedding is more than 0 we can make one of the choices. Choice 1: bad edge e =(x, y)where x and y arebad vertices. In this case W1 = W2 = W3 = W4. To calculate the modi.eddefect of the embedding of Gi+1 observe thatbad edges in the embedding of Gi+1 are bad edges of the embedding of Gi minus e plus bad pairs {(70), (01)}, {(12), (23)}, {(34), (45)} and {(56), (67)}. So d(.(Gi+1))= d(.(Gi))-1+4 = d(Gi)+3. Since we removed twobad vertices x and y and created no newbad vertices wehave dv (.(Gi+1))= dv (.(Gi))-2 and therefore the modi.eddefectis d ' (.(Gi+1)). d ' (.(Gi))-1. We conclude that d ' (Gi+1). d ' (Gi)-1. Choice 2: bad edge with e =(x, y)where x is a bad vertex and y is not. In this case W1 == W4 and W2 .W1. W3 = The defect of the induced embedding of Gi+1 is d(.(Gi+1)= d(.(Gi))- 1+2 = d(Gi)+1 and dv (.(Gi+1)= dv(.(Gi))-1. Therefore the modi.ed defectis d ' (.(Gi+1))= d ' (.(Gi))-1. We conclude that d ' (Gi+1). d ' (Gi)-1. Choice 3: bad edge e =(x, y)which appears twice along one facial walk. Since we can not make choices 1 or 2 we can assume that W1 = W3 and W2 .W1 and W4 = W1 (but it is possible thatW2 = W4). In the embeddings of Gi and Gi+1 there are no bad vertices. The defect of the embedding of Gi+1 is d(.(Gi+1)= d(.(Gi))-1 and therefore d ' (Gi+1). d ' (Gi)-1. Choice 4: e =(x, y) which does not appear twice along one facial walk. Since we can notmake choices1,2, or3itis onlypossiblethat maybe W2 = W4. In the embeddings of Gi and Gi+1 there are no bad vertices. The defect of the embedding of Gi+1 is d(.(Gi+1)= d(.(Gi))-1 and therefore d ' (Gi+1). d ' (Gi)-1. It remains to show that r(Gi+1). r(Gi)-2. Suppose we have a minimum coloring c of the graph Gi+1. We de.ne a coloring c ' of Gi as follows: c ' (e)= c(e) if e is not incident with x or y, and we let c ' (x1x)= c(x16), c ' (yy2)= c(2y2). We can color the edge e with one of the colors 1, 2, 3 and color edges x20 and y14 with color 4. So r(Gi). r(Gi+1)+2. ThelasttheoremimpliesthatifGr¨unbaum conjectureistrue, we canbound d ' (G)frombelow withr(G),whichwouldbeavery strong connectionbetween the defect, which is a topological property, and resistance, which is a coloring 4.3 Defect and Gr¨unbaum conjecture property. We conclude with thefollowingproblems, which couldbe considered as a weakening of the Gr¨unbaum conjecture: Problem 4.8. Is there a nondecreasing function f with limx›. f(x)= ., such that d ' (G). f(r(G))for all cubic graphs. Problem 4.9. Find a constant c> 0 such that d ' (G) . cr(G) for all cubic graphs. Bibliography [1] B. Mohar, C. Thomassen, Graphs on Surfaces, The Johns Hopkins Uni­versity Press, Baltimore and London, 2001. [2] J. Petersen, Sur le th´eor`eme de Tait, L’Interm´ediaire des Math´ematiciens 5(1898), 225-227. [3] D.Blanuˇsa,Problemˇcetirijuboja,GlasnikMat.–Fiz. Astr.Ser2(1946), 31–42. [4] B. Gr¨unbaum, Conjecture 6, in Recent Progress in Combinatorics, Ed. W. T. Tutte, Academic Press, New York, 1969, 343. [5] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc. 8(1973), 367–387. [6] G.Szekeres, Non-colourabletrivalentgraphs,CombinatorialMathematics (Proc.Third Austral.Conf., Univ.Queensland,St.Lucia,1974),Lecture Notes in Math., Vol. 452, Springer, Berlin, 1975, 227–233. [7] R.Isaacs,In.nitefamiliesofnontrivial trivalentgraphswhich arenotTait colorable, Amer.Math.Monthly 82(1975),221–239. [8] K. Appel, W. Haken, Every planar map is four colorable. I. Discharging, IllinoisJ.Math.21(1977), no.3,429–490. [9] K. Appel, W. Haken, J. Koch, Every planar map is four colorable. II. Reducibility,IllinoisJ.Math.21(1977), no.3,491–567. [10] F. Jeager, T. Swart, Conjecture 1, Combinatorics 79 (M. Deza and I.G.Rosenberg,Eds.), Ann.Disc.Math.,Vol.9,p.305,ProblemSession, Amsterdam, 1980. [11] M. K. Goldberg, Construction of class 2 graphs with maximum vertex degree 3, J. Comb. Theory Ser. B 31(1981), 282–291. 75 [12] F. C. Tinsley, J. J. Watkins, A study of snark embeddings, Graphs and applications(Boulder, Colo., 1982), 317–332, Wiley-Intersci. Publ., 1985. [13] P.J.Cameron,A.G.Chetwynd,J.J.Watkins,Decompositionsof snarks, J. Graph Theory 11(1987), 13–19. [14] N. Robertson, R. P. Vitray, Representativity of surface embeddings, in: Paths, Flows, and VLSI-Layout, B. Korte, L. Lov´asz, H. J. Pr¨omel, and A. Schrijver Eds., Springer-Verlag, Berlin, 1990, 293–328. [15] B. Mohar, Combinatorial local planarity and the width of graph embed­dings,Canad.J. ofMath.44(1992),1272–1288. [16] D. A. Holton, J. Sheehan, The Petersen Graph, Austral. Math. Soc. Lec­ture Series 7, Cambridge University Press, 1993. [17] M. Kochol, Snarks without small cycles, J. Comb. Theory Ser. B 67 (1996), no. 1, 34–47. [18] N. Robertson, D. Sanders, P. Seymour, R. Thomas, The four color theo­rem,J.Comb.Theory Ser.B70(1997), no.1,2–44. [19] A. Cavicchioli, M. Meschiari, B. Ruini, F. Spaggiari, A Survey on Snarks and New Results: Products, Reducibility and a Computer Search, J. Graph Theory 28(1998), 57–86. [20] E. Ste.en, Measurements of edge-uncolorability, Discrete Math. 280 (2004), 191–214. [21] A. Orbani´c, T. Pisanski, M. Randi´c, B. Servatius, Blanuˇsa double, Math. Commun.9(2004), no.1,91–103. [22] B. Mohar, A. Vodopivec, On polyhedral embeddings of cubic graphs, Comb., Prob. Comp.(2006) 15, 877–893. [23] A.Vodopivec,Onembeddingsof snarksinthetorus,toappearinDiscrete Math. [24] http://www.cs.uwa.edu.au/~gordon/remote/cubics/index.html Razˇsirjeni povzetek De.nicije Graf G je podan s parom mnoˇzic V (G) in E(G). Mnoˇzica V (G)je konˇcna mnoˇzica vozliˇsˇc ali toˇck grafa G, E(G) pa mnoˇzica povezav. Povezava grafa G je mnoˇzica {u, v}, krajˇse uv, kjer sta u, v . V (G)vozliˇsˇci grafa G. Vozliˇsˇci u in v sta povezani, ˇceje e = uv . E(G). Vozliˇsˇcu v reˇcemo soseda toˇcke u. ˇ Vozliˇsˇci u in v sta krajiˇsˇci povezave e. Stevilu sosed vozliˇsˇca v reˇcemo stopnja vozliˇsˇca. Najveˇcjo stopnjo vozliˇsˇca grafa G oznaˇcimo z .(G). Za povezavi, ki vsebujeta kako skupno vozliˇsˇce, reˇcemo da sta sosednji vozliˇsˇci. Vsi gra. ˇ so enostavni, torej ne vsebujejo veˇckratnih povezav niti zank. Ce v grafu dovolimo veˇckratne povezave ali zanke, govorimo o multigrafu. k-barvanje povezav grafa G je preslikava c : E(G) ›{1, 2,...,k}, ki so­ˇ sednjima povezavama priredi razliˇcni ˇstevili. Stevilom {1, 2,...,k} reˇcemo barve. Najmanjˇsemu ˇstevilu k, za katerega obstaja k-barvanje povezav grafa G, reˇcemo kromatiˇcni indeks grafa G in ga oznaˇcimo s . ' (G). Za enostavne grafe velja: Izrek 1(Vizing). Za enostaven graf G je. ' (G).{.(G), .(G)+1}. Grafom, za katere velja . ' (G)= ., reˇcemo gra. razreda 1, grafom, za katere velja . ' (G)=.(G)+1,pa reˇcemo gra. razreda 2. ˇ Ce je stopnja vsakega vozliˇsˇca grafa G enaka k, je graf Gk-regularen . 3-regularnim grafom reˇcemo kubiˇcni gra.. ˇ Ce za vsaki vozliˇsˇci u, v . V (G)obstaja pot P = v0v1 ··· vn, kjer sta toˇcki vi in vi+1, i =0,...,n - 1 povezani, in je v0 = u ter vn = v, je graf G povezan. Maksimalni povezani podmnoˇzici grafa G reˇcemo komponenta grafa G. Za podmnoˇzico S . E(G)oznaˇcimo z G -S graf z mnoˇzico vozliˇsˇc V (G) in mnoˇzico povezav E(G)\S. Podmnoˇzica S . E(G)jeprerez, ˇce ima graf ˇ G -S veˇc komponent kot graf G. Ceje velikost vsakegaprerezapovezanega grafa G vsaj k,je G povezavno k-povezan . Podmnoˇzica S . E(G)jecikliˇcni prerez, ˇce ima graf G - S vsaj dve komponenti, ki vsebujeta cikel. Povezan 77 graf G jecikliˇcno k-povezan , ˇce ima vsak cikliˇcni prerez grafa G velikost vsaj k. Slika 4.8: Petersenov graf. Kubiˇcnigraf razreda2,kije3-povezan, cikliˇcno4-povezan zdolˇzino naj­krajˇsega cikla vsaj 5, se imenuje snark. Ime so snarki dobili po pesmi The Hunting of the Snark avtorjaLewisaCarrolla,vkateri so snarkipoˇsasti,kijih jezeloteˇzkonajti. Najmanjˇsi snarkjePetersenovgraf(glej sliko4.8),kiima 10 vozliˇsˇc. Odkrili sogakonec18. stoletja[2]. Naslednjaodkrita snarka sta Blanuˇseva snarka,kijujeleta1946 odkrilhrvaˇski matematikBlanuˇsa[3](glej sliko 4.9). To so edini trije snarki z manj kot 20 toˇckami. Prva znana neskonˇcna druˇzina snarkov so bili snarki, ki jih dobimo kot 4-vsote manjˇsih snarkov, odkrita pa je bila v sedemdesetih letih prejˇsnjega stoletja [7]. Denimo da sta G1 in G2 kubiˇcna grafa. Naj bosta e, f nesose­dnji povezavi grafa G1 in u, v sosednji vozliˇsˇci grafa G2. Oznaˇcimo z v1,v2 krajiˇsˇcipovezave e in z v3,v4 krajiˇsˇcipovezave f. Sosedi toˇcke u, razliˇcni od v, oznaˇcimo z u1,u2 in sosedi toˇcke v, razliˇcni od u, oznaˇcimo z u3 in u4. Grafu G1 odstranimo povezavi e, f, grafu G2 ostranimo vozliˇsˇci u, v in dodamo po­vezave viui, i =1, 2, 3, 4. Dobimo kubiˇcen graf G = G1 · G2, ki ga imenujemo 4-vsota grafov G1 in G2. Prerezu {viui | i =1, 2, 3, 4}reˇcemo prerez 4-vsote. ˇ Ce sta G1 in G2 snarka,potemjenjuna4-vsotatudi snark. Veljatudi obrat: ˇce ima snark G cikliˇcni prerez S velikosti 4, potem obstajata taka grafa G1 in G2, daje G = G1 · G2, vsaj eden od G1 in G2 je snark in S prerez 4-vsote ˇ G. Oˇcitno 4-vsota grafov ni enoliˇcno doloˇcena. Ce za G1 in G2 vzamemo dve kopijiPetersenovegagrafa,lahkokonstruiramodve neizomorfni4-vsoti. Izkaˇze Razˇsirjeni povzetek Slika 4.9: Blanuˇseva grafa. se,da statoravnoBlanuˇsevagrafa. 4-vsotopripisujejoIsaacsu,jojepapred njim opisal ˇze ruski matematik Titus, a njegov ˇclanek na zahodu ni poznan. Isaacsjeopisalˇsedruˇzinocikliˇcno6-povezanih snarkov,kijihimenujemo cvetni snarki (glejsliko 4.10). Cvetni snark J2k+1 je grafz mnoˇzico vozliˇsˇc V (J2k+1)= {ai,bi,ci,di | i =0,..., 2k} in mnoˇzico povezav E(J2k+1)= {aiai+1,aibi,bici,bidi,cidi+1,dici+1 | i =0,..., 2k}, kjer so indeksi vzeti po modulu 2k +1. Naslednjo neskonˇcnodruˇzinoje odkrilGoldberg[11]. Goldergovgraf G2k+1 (glejsliko4.10)jegraf zmnoˇzicovozliˇsˇc V (G2k+1)= {ai,bi,ci,di,ei,fi,gi,hi | i =0,..., 2k} in mnoˇzico povezav E(G2k+1)= {aiai+1,aibi,bici,bidi,ciei,cigi, difi,dihi,gihi,eifi,fiei+1,gihi+1 | i =0,..., 2k}, kjer so indeksi vzeti po modulu 2k +1. CvetniinGoldbergovisnarki sokonstruirani tako,dalihoˇstevilopodgrafov Yi oziroma Ti, induciranih na vozliˇsˇcih {ai,bi,ci,di}oziroma {ai,bi,ci,di,ei,fi, ˇ gi,hi} cikliˇcno poveˇzemo med seboj. Ce pri de.niciji cvetnih oziroma Gold­bergovih snarkovnezahtevamo,daimamolihoˇstevilotehpodgrafov,dobimo sploˇsnejˇse grafe Jk in Gk. Gra. J2k in G2k so razreda 1. Vzemimo druˇzino poligonov s stranicami dolˇzine 1, ki imajo skupaj sodo ˇstevilo stranic .1,...,.2n. Vsaki stranici izberemo orientacijo tako, da si izbe­remo zaˇcetno ogliˇsˇce stranice. Izberemo si particijo stranic na pare. Konstru­irajmo ploskev tako, da identi.ciramo stranice skladno z izbrano orientacijo (zaˇcetne toˇcke identi.ciramo z zaˇcetnimi toˇckami). Dobimoploskev S. Grafu, kiga de.nirajo ogliˇsˇcaploskve S in stranicekotpovezave,reˇcemo vloˇzengraf . Celiˇcna vloˇzitev grafa G je je vloˇzen graf G ' , izomorfen grafu G. Zaˇcetne poligone imenujemo lica vloˇzitve. Lica identi.ciramo s sprehodi, de.nirani z obhodi lic. Poklasi.kaciji sklenjenihploskevjevsakaploskevizomorfnanatankoeni od ploskev Sg (orientabilniploskviroda g)oziroma Ng (neorientabilniploskvi roda g). Orientabilni rod g(G) grafa G je najmanjˇsi g, za katerega obstaja vloˇzitev grafa G v ploskev izomorfno Sg . Neorientabilni rod g~(G) grafa G je najmanjˇsi g, zakaterega obstaja vloˇzitevgrafa G v Ng . Eulerjevakarakteristika Razˇsirjeni povzetek Slika 4.10: Cvetni snark J5 (zgoraj)in Goldbergov snark G5 (spodaj). orientabilne ploskve Sg je o(Sg)=2g, Eulerjeva karakteristika neorientabilne ploskve Ng paje o(Ng )= g. Vloˇzitev grafa G je poliedrska, ˇce je vsako lice cikel in ˇce sta vsaki dve razliˇcni lici bodisi disjunktni, se sekata v natanko enem vozliˇsˇcu ali pa se sekata v natanko enipovezavi. Vloˇzitevkubiˇcnegagrafajepoliedrska,ˇceje vsako lice cikel in ˇce sta vsaki dve razliˇcni lici disjunktni ali pa se sekata v natanko eni povezavi. Motivacija za ˇstudij vloˇzitev snarkov prihaja iz poskusov dokaza izreka ˇstirih barv. Izrek ˇstirih barv pravi, da lahko vozliˇsˇca vsakega ravninskega grafa brez zank pobarvamo s ˇstirimi toˇckami tako, da sta vsaki sosednji vo­zliˇsˇci pobarvani z razliˇcnima barvama. Tutte je pokazal, da je izrek ˇstirih barv ekvivalenten trditvi, da ima vsak 3-povezan kubiˇcen graf G v ravnini kromatiˇcni indeks . ' (G)=3. Izrekˇstirihbarvtrdi,da snarki nisoravninskigra.. Snarkelahkovloˇzimo v ploskve viˇsjega roda, vendar imajo vse znane vloˇzitve lice, ki vsebuje kako povezavo dvakrat, ali pa dve lici, ki se sekata v veˇc kot eni povezavi. Torej vloˇzitve nisopoliedrske. Gr¨unbaumjeleta1969podalhipotezo Hipoteza 2(Gr¨unbaum). ˇcengrafpoliedrskovloˇ Ce ima kubiˇzitev v orien­tabilnoploskev,potemje razreda1. Gr¨unbaumova hipotezaje posploˇsitev izrekaˇstirih barv. Rod snarkov Rod snarkov sta ˇstudirala Tinsley in Watkins [12]. Pokazala sta, da je ori­entabilni rod cvetnih snarkov enak g(J2k+1)= k. V prvem poglavju podamo krajˇsidokaz njunega rezultatain hkratiizraˇcunamo neorientabilni rod cvetnih snarkov. Izrek 3. Orientabilni rod cvetnega snarka J2k+1 jeg(J2k+1)= k. Neorienta­bilni rod cvetnega snarka J2k+1 je g~(J2k+1)=2k -1. Orientabilni rod grafa J2k jeg(J2k)= k -1, neorientabilni rod pa g~(J2k)=2k -2. Tinsley inWatkins stapodalazgornjomejozaorientabilni rodGoldbergo­vih snarkov. Pokaˇzemo,dajenjunamejavresnici orientabilni rodGoldber­govih snarkov. Doloˇcimoˇseneorientabilni rodGoldbergovihgrafov. Izrek 4. Orientabilni rod Goldbergovega grafa Gk je g(Gk)= k - 1. Neori­entabilni rod Goldbergovega grafa Gk jeg~(Gk)= k. Razˇsirjeni povzetek Teˇzji del dokaza zadnjih dveh izrekov je dokaz spodnje meje za rod. V obehprimerihpridokazu omejimoˇstevilolic,kijihlahkoimamo v vloˇzitvah, in tako dobimo mejo za rod s pomoˇcjo Eulerjeve formule. Lica razdelimo na lokalna in globalna lica in pokaˇzemo, da v vloˇzitvah ne moremo imeti veliko lokalnih lic. V istem ˇclanku sta Tinsley in Watkins postavila hipotezo o orientabilnem rodu 4-vsot Petersenovih snarkov. S P n oznaˇcimo 4-vsoto n kopij Peterseno­vegagrafa. Tinsley inWatkins stadomnevala,daje g(P n)= n -1. Hipoteza jebilaovrˇzenav[21],kjer soavtorjipokazali,daimaedenodBlanuˇsevih snar­kovrod1,drugipa2. Rodjetorej lahkoviˇsji oddomnevanega. Pokaˇzemo, dajelahkotudi veliko manjˇsi oddomnevanega. Izrek 5. Za vsak n> 0 obstaja 4-vsota n kopij Petersenovega grafa, ki ima rod 1. n Prikonstrukciji P n = P · P n-1 jelahko rodgrafaP enak rodugrafa P n-1 , alipa serodpoveˇcaza1. Raziˇsˇcemopogoje,prikaterih serod4-vsotepoveˇca in pogoje, pri katerih se rod ne spremeni. Tako lahko konstruiramo 4-vsoto n kopij Petersenovega grafa, za katero lahko natanˇcno povemo njen orientabilni rod. Izrek 6. Za vsako celo ˇstevilo k, 1 . k . n obstaja 4-vsota n kopij Peterse­novega grafa P n, ki ima rod g(P n)= k. Nakoncupokaˇzemoˇse meje za orientabilni rod4-vsotepoljubnihkubiˇcnih grafov. Izrek 7. Za kubiˇcna grafa G1 in G2 je rod 4-vsoteG1 · G2 omejen z g(G1)+g(G2)-2 . g(G1 · G2). g(G1)+g(G2)+1. Meje so najboljˇse moˇzne, tudi ˇce zahtevamo, da sta G1 in G2 snarka. Poliedrske vloˇzitve Najprej pokaˇzemo, da so kratki cikli v poliedrskih vloˇzitvah lica. Lema 8. • ˇcnem grafu G, potemje C obhod lica v Ceje C 3-cikel v kubiˇ vsaki poliedrski vloˇzitvi grafa G. • ˇ Ce je C 4-cikel v kubiˇcnem grafu G, potem je C obhod lica v vsaki poliedrski vloˇzitvi grafa G. ˇ Ce je C cikel v grafu in F obhod lica, potem reˇcemo da je F pri Ck­napredujoˇc obhod, ˇce se C in F sekata na k zaporednih povezavah na obhodu F . Lema 9. ˇcnem grafu G, potemje Ceje C 5-cikel v kubiˇ • v vsaki poliedrski vloˇzitvi grafa G v orientabilno ploskev cikel C obhod lica, • v vsaki poliedrski vloˇzitvi G v neorientabilno ploskev cikel C ali obhod lica alipaje vsakolice2-napredujoˇcepri C. Naj bosta G1 in G2 kubiˇcna grafa in v . V (G1)ter u . V (G2). Oznaˇcimo sosede vozliˇsˇca v v G1 z v1,v2,v3 in sosede vozliˇsˇca u v G2 z u1,u2,u3. Grafu G1 odstranimo vozliˇsˇce v skupaj z njenimi povezavami, grafu G2 odstranimo vozliˇsˇce u skupaj z njenimi povezavami ter dodamo povezave uivi, i =1, 2, 3. Dobimo kubiˇcen graf G = G1 * G2, ki ga imenujemo 3-vsota grafov G1 in G2. Izrek 10. Najbo G 3-vsotagrafov G1 ter G2. Graf G imapoliedrsko vloˇzitev (v orientabilno ploskev) natanko tedaj ko imata grafa G1 ter G2 poliedrski vloˇzitvi(v orientabilniploskvi). Posledica zadnjegaizrekaje,dajeGr¨unbaumovohipotezodovolj pokazati za cikliˇcno 4-povezane grafe. Po Lemi 8 je Gr¨unbaumovo hipotezo dovolj pokazati za grafe z najkrajˇsim ciklom dolˇzine vsaj 4. SpomoˇcjoLeme9lahkozaGoldbergove snarkepokaˇzemo,danimajopoli­edrskih vloˇzitev v orientabilne ploskve. To sledi iz dejstva, da imamo v Gold­bergovihgra.h5cikla natoˇckah bidifieicibi inbicigihidibi. Vpoliedrskivloˇzitvi vorientabilnoploskev staoba5-ciklaobhodalic,topani mogoˇce, sajjevtem primeru pot cubidi dolˇzine 3 vsebovana v dveh razliˇcnih obhodih lic. Dacvetni snarki nimajopoliedrskih vloˇzitevvorientabilneploskvejepo­kazalˇzeSzekeres. Podamoenostavnejˇsidokaztetrditve. Hkratipokaˇzemo,da cvetni snarki J2k+1, k> 1, nimajo poliedrskih vloˇzitev v neorientabilne plo­skve. Graf J3 ima poliedrsko vloˇzitev v projektivno ravnino, vendar ni snark, saj vsebuje cikel dolˇzine 3. Sledi izrek: Izrek 11. • Cvetni snarki nimajo poliedrskih vloˇzitev niti v orientabilne niti v neorientabilne ploskve. • Goldbergovi snarki nimajo poliedrskih vloˇzitev v orientabilne ploskve. PridokazuIzreka11 neuporabimodejstva,da sogra.razreda2. Istidokaz pove, da tudi gra. J2k nimajo poliedrskih vloˇzitev. Za Goldbergove snarke konstruiramo poliedrske vloˇzitve v neorientabilne ploskve. Poliedrska vloˇzitev grafa Gk v neorientabilno ploskev je podana z naslednjimi obhodilic(indeksi sopomodulu k) Razˇsirjeni povzetek • A = a0a1 ...ak-1a0 in B = f0e0f1e1 ...fk-1ek-1f0, • Ci = bidifieicibi, i =0,...,k -1, • Di = gihigi+1hi+1di+1fi+1eicigi, i =0,...,k -1, • Ei = aiai+1bi+1ci+1gi+1hidibiai, i =0,...,k -1. Zgoraj opisana vloˇzitev ima rod k. Za Goldbergove snarke konstruiramo tudi poliedrske vloˇzitve v neorientabilne ploskve roda k +2. Iz znanih poliedrskih vloˇzitev lahko konstruiramo nove poliedrske vloˇzitve snarkov s pomoˇcjo 4-vsote. Izrek 12. Najbosta G1 inG2 kubiˇcnagrafa. ˇ CeimataG1 inG2 takipoliedrski vloˇzitvi v(orientabilni) ploskvi S1 in S2, da dual grafa G2 v S2 ni poln graf, potem obstaja 4-vsota G1 · G2, ki ima poliedrsko vloˇzitev v (orientabilno) ˇ ploskev S. Ce je Eulerjev rod ploskev o(S1)= k1 in o(S2)= k2, potem je Eulerjev rod ploskve S enak o(S)= k1 + k2. Velja tudi obrat: Izrek 13. Naj bo G kubiˇcen graf s cikliˇcnim 4-prerezom S ki ima poliedrsko vloˇzitev. Potem obstajata taka kubiˇcnagrafa G1 in G2, daje G 4-vsotagrafov G1 in G2 ter daje S prerez 4-vsote. Vsaj eden od G1 in G2 ima poliedrsko vloˇzitev. Goldbergovi snarkiimajopoliedrskevloˇzitvevneorientabilneploskveroda 2k +1, Petersenov graf pa ima poliedrsko vloˇzitev v projektivno ravnino. S pomoˇcjo Izreka 12 dobimo posledico: Posledica 14. Za vsakonenegativnoceloˇstevilo k obstaja snark spoliedrsko vloˇzitvijo v neorientabilno ploskev Nk roda k. Pri dokazu posledice posebej obravnavamo Kleinovo steklenico, saj Izreka 12 ne moremo uporabiti za dve kopiji Petersenovega grafa, vloˇzeni v projek­tivno ravnino. Snark s poliedrsko vloˇzitvijo v Kleinovo steklenico dobimo kot superpozicijo Petersenovega grafa. Degeneriranost Naj bo G kubiˇcengrafin. vloˇzitevgrafa G v orientabilnoploskev. Za obhod lica F v vloˇzitvi . de.niramo degeneriranost d(F ) kot ˇstevilo povezav grafa G, ki nastopajo dvakrat na obhodu F . Za dva razliˇcna disjunktna obhoda lic Fi in Fj de.niramo degeneriranost d(Fi,Fj )= Ce imata obhoda lic Fi in Fj 0. ˇkako skupnopovezavo,de.niramodegeneriranostd(Fi,Fj )kotˇstevilopovezav, ki nastopajo hkrati na obhodu Fi in Fj , minus 1. Naj ima vloˇzitev . mnoˇzico obhodovlic F = {F1,F2,...,Fk}. Potemde.niramo degeneriranost vloˇzitve . kot k d(.)= d(Fk)+ d(Fi,Fj ) i=1 1.i