Genus, planarity
7a. Planar graphs
Remember the discussion from the opening of chapter 4, regarding good and bad graphs. We have seen there that a nice and fruitful notion of “goodness”, coming from simple and beautiful things like the circulant graphs, is the notion of transitivity.
On the other hand, we have just seen that trees are beautiful and good as well, from an opposite aesthetic to that of the circulant graphs. So, question now for the two of us, subjective as they come: thinking deeply, what makes the beauty of a tree?
You might agree with this or not, but here is an answer to this question:
\begin{answer} Graphs fall into three classes:
- Trees and other graphs which can be drawn without crossings are good.
- If we can still do this, but on a torus, the graph is bad.
- And the rest is evil.
\end{answer} Here the fact that trees are indeed planar is obvious, and as an illustration, here is some sort of “random” tree, which is clearly planar, no question about it:
Of course, there are many other interesting examples of planar graphs. Consider for instance our beloved cube graph, that we met on many occasions, in the above:
At the first glance, this graph does not look very planar. However, after thinking a bit, we can draw it as follows, making it clear that this graph is planar:
Of course, not all graphs are planar. In order to find basic examples of non-planar graphs, we can look at simplices, and we are led to the following result:
When looking at simplices, the segment [math]K_2[/math], the triangle [math]K_3[/math] and the tetrahedron [math]K_4[/math] are planar. However, the next simplex [math]K_5[/math], namely
This is something quite elementary and intuitive, as follows:
(1) The graphs [math]K_2,K_3,K_4[/math] are indeed planar, with this being clear for [math]K_2,K_3[/math], and with the planarity of [math]K_4[/math] being shown by the following picture for it:
(2) Regarding now the non-planarity of [math]K_5[/math], let us try to manufacture an intuitive proof for this. In order to draw [math]K_5[/math] in a planar way, we first have to draw its subgraph [math]K_4[/math] in a planar way, and it is pretty much clear that this can only be done as a variation of the above picture, from (1), with curved edges this time, as follows:
But with this in hand, it is clear that there is no room in the plane for our 5th vertex, as to avoid crossings. Indeed, we have 4 possible regions in the plane for this 5th vertex, and each of them is forbidden by the edge towards a certain vertex, as follows:
(3) Finally, the fact that the graphs [math]K_N[/math] with [math]N\geq6[/math] are not planar either follows from the fact that their subgraphs [math]K_5[/math] are not planar, that we know from (2).
In order to find some further examples of non-planar graphs, we can look as well at the bipartite simplices, and we are led to the following result:
When looking at bipartite simplices, the square [math]K_{2,2}[/math] is planar, and so are all the graphs [math]K_{2,N}[/math]. However, the next such graph, namely [math]K_{3,3}[/math],
Again, this is something elementary and intuitive, as follows:
(1) In what regards the first bipartite simplex, which is [math]K_{2,2}[/math], this is indeed the square, which is of course a planar graph, as shown by the following equality:
(2) Regarding now the bipartite simplex [math]K_{2,N}[/math] with [math]N\geq2[/math] arbitrary, this graph looks at follows, with [math]N[/math] vertices in the lower row:
But this graph is planar too, because we can draw it in the following way:
(3) Regarding now [math]K_{3,3}[/math], as before with the simplex [math]K_5[/math], the result here is quite clear by thinking a bit, and drawing pictures. To be more precise, reasoning by contradiction, we first have to draw its subgraph [math]K_{2,3}[/math] in a planar way, and this is done as follows:
(4) But now, as before with [math]K_5[/math], it is clear that there is no room in the plane for our 6th vertex, as to avoid crossings. Indeed, we have 3 regions in the plane for this 6th vertex, and each of them is forbidden by the edge towards a certain vertex, as follows:
Thus, theorem proved for the utility graph [math]K_{3,3}[/math], via the same method as for [math]K_5[/math].
(5) Still talking [math]K_{3,3}[/math], let us mention that this is called indeed “utility graph”, as said above, due to a certain story with it. The story involves 3 companies, selling gas, water and electricity to 3 customers, and looking for a way to arrange their underground tubes and wires as not to cross. Thus, they are looking to implement their “utillity graph”, which is [math]K_{3,3}[/math], in a planar way, and unfortunately, this is not possible.
(6) And as further comments on [math]K_{3,3}[/math], quite remarkably, in recent years the stocks of the above-mentioned 3 companies have skyrocketed, apparently due to very good business done by their Saturn ring branches, which were able to considerably cut from their costs. But are we here for talking about economy, or about mathematics.
(7) Finally, the bipartite simplex [math]K_{M,N}[/math] with [math]M,N\geq3[/math] is not planar either, because it contains [math]K_{3,3}[/math]. Thus, we are led to the conclusions in the statement.
So long for planar graphs, which are the “good” ones, in the sense of Answer 7.1. But, what about the graphs which are bad, or evil, in the sense of Answer 7.1? It is pretty much clear that their mathematics is quite complicated, and more on this later, but in the meantime, in regards with the graphs [math]K_N[/math] and [math]K_{M,N}[/math], let us formulate:
The simplices [math]K_N[/math] and bipartite simplices [math]K_{M,N}[/math] with [math]M\leq N[/math] are as follows, with respect to our good, bad and evil classification scheme:
- The good, planar graphs are [math]K_2,K_3,K_4[/math] and [math]K_{2,N}[/math].
- The bad graphs, that can be drawn however on a torus, are [math]K_5,K_6,K_7[/math] and [math]K_{3,3},K_{3,4},K_{3,5},K_{3,6}[/math], and [math]K_{4,4}[/math].
- As for the remaining graphs, these are all evil, not drawable on a torus.
This does not look easy at all, so basically theorem coming without proof, and more on this later. However, in the meantime, some remarks about all this:
(1) What we know so far, from Proposition 6.2 and Proposition 6.3, is that (1) holds. Not bad, and it remains to decide, for the remaining graphs, if these are bad or evil.
(2) Regarding the fact that the graphs in (2) are indeed bad, that is, drawable on a torus, this is normally not difficult, just requiring some silence, thinking, and patience. Indeed, to start with, there is no really need to bother with 3D pictures for the torus, because this torus appears from a rectangle, by gluing the opposite sides, as follows:
(3) With this drawing method in hand, let us first look at [math]K_5[/math]. After some thinking, this graph is indeed toral, because it can be drawn on a torus as follows, with the convention that the dotted edges connect, according to our gluing conventions above:
(4) A similar method works for the bipartite simplex [math]K_{3,3}[/math], with this graph being drawable on a torus as follows, with our various pictorial conventions above:
(5) Thus, theorem fully proved for the basic non-planar graphs, namely [math]K_5,K_{3,3}[/math]. In what regards [math]K_6,K_7[/math], and then [math]K_{3,4},K_{3,5},K_{3,6}[/math], and then [math]K_{4,4}[/math], we will leave drawing them on a torus as an instructive exercise, that is, 6 graphs, say 1/2 hour each. Of course you might say that it is enough to do it for [math]K_7,K_{3,6},K_{4,4}[/math], but don't be greedy, if you try directly these 3 graphs, these might well cost you 2 hours each, so no gain.
(6) As for the graphs left, here we just have to prove that [math]K_8,K_{3,7},K_{4,5}[/math] are evil. This is something a bit more difficult, requiring extreme silence, thinking, and patience, and as before, we will leave this as an instructive exercise, of rather difficult type.
(7) We will be of course back to this, later in this chapter, but in meantime, you might wonder if there is something more conceptual, say some kind of “formula”, behind all this. And in answer, yes there is a formula. The idea is that associated to any graph is a certain positive integer [math]g\in\mathbb N[/math], called genus, which is as follows:
(8) In general, the genus is quite hard to compute, and more on this later. However, coming a bit in advance, the genus of [math]K_N[/math] is indeed computable, given by the following formula, with [math]\lceil x\rceil[/math] being the ceiling function, that is, the smallest integer [math]\geq x[/math]:
And for [math]N=4,5,6,7,8[/math], this gives the following values, which are what we need:
(9) As for the bipartite simplices, [math]K_{M,N}[/math] with [math]M\leq N[/math], here again the genus is explicitly computable, with appropriate tools, the formula being as follows:
And at [math]M=3[/math] and [math]N=2,3,4,5,6,7[/math], and [math]M=4[/math] and [math]N=4,5[/math] we get, as needed:
But more on such things, which are quite technical, later in this chapter.
7b. Main theorems
Let us get back now to the planar graphs, and try to develop some systematic theory for them. As a first main result about these graphs, we have:
The fact that a graph [math]X[/math] is non-planar can be checked as follows:
- Kuratowski criterion: [math]X[/math] contains a subdivision of [math]K_5[/math] or [math]K_{3,3}[/math].
- Wagner criterion: [math]X[/math] has a minor of type [math]K_5[/math] or [math]K_{3,3}[/math].
This is obviously something quite powerful, when thinking at the potential applications, and non-trivial to prove as well, the idea being as follows:
(1) Regarding the Kuratowski criterion, the convention is that “subdivision” means graph obtained by inserting vertices into edges, e.g. replacing [math]\bullet-\bullet[/math] with [math]\bullet-\bullet-\bullet[/math].
(2) Regarding the Wagner criterion, the convention there is that “minor” means graph obtained by contracting certain edges into vertices.
(3) Regarding now the proofs, the Kuratowski and Wagner criteria are more or less equivalent, and their proof is via standard, although long, recurrence methods.
(4) In short, non-trivial, but rather routine results that we have here, and we will leave finding and studying their complete proofs as an instructive exercise.
(5) Finally, let us mention that, often in practice, Wagner works a bit better than Kuratowski. More on this in a moment, when discussing examples.
Regarding now the applications of the Kuratowski and Wagner criteria, things are quite tricky here, because most of the graphs that we met so far in this book are trees and other planar graphs, for which these criteria are not needed. We have as well the graphs [math]K_N[/math] and [math]K_{M,N}[/math], to which these criteria apply trivially. Thus, for illustrations, we have to go to more complicated graphs, and as a standard example here, we have:
The Petersen graph [math]P[/math], namely
- Kuratowski: [math]P[/math] contains no subdivision of [math]K_5[/math], but contains a subdivision of [math]K_{3,3}[/math].
- Wagner: [math]P[/math] has both [math]K_5[/math] and [math]K_{3,3}[/math] as minors.
{{{4}}}
The above result is quite interesting, the Petersen graph being a key object in combinatorics, usually providing counterexamples to all sorts of graph theory statements that can be made. We will be back to this graph later, with a proof that it is toral.
As a second main result now about the planar graphs, we have:
For a connected planar graph we have the Euler formula
This is something very standard, the idea being as follows:
(1) Regarding the precise statement, given a connected planar graph, drawn in a planar way, without crossings, we can certainly talk about the numbers [math]v[/math] and [math]e[/math], as for any graph, and also about [math]f[/math], as being the number of faces that our graph has, in our picture, with these including by definition the outer face too, the one going to [math]\infty[/math]. With these conventions, the claim is that the Euler formula [math]v-e+f=2[/math] holds indeed.
(2) As a first illustration for how this formula works, consider a triangle:
Here we have [math]v=e=3[/math], and [math]f=2[/math], with this accounting for the interior and exterior, and we conclude that the Euler formula holds indeed in this case, as follows:
(3) More generally now, let us look at an arbitrary [math]N[/math]-gon graph:
Then, for this graph, the Euler formula holds indeed, as follows:
(4) With these examples discussed, let us look now for a proof. The idea will be to proceed by recurrence on the number of faces [math]f[/math]. And here, as a first observation, the result holds at [math]f=1[/math], where our graph must be planar and without cycles, and so must be a tree. Indeed, with [math]N[/math] being the number of vertices, the Euler formula holds, as:
(5) At [math]f=2[/math] now, our graph must be an [math]N[/math]-gon as above, but with some trees allowed to grow from the vertices, with an illustrating example here being as follows:
But here we can argue, again based on the fact that for a rooted tree, the non-root vertices are in obvious bijection with the edges, that removing all these trees won't change the problem. So, we are left with the problem for the [math]N[/math]-gon, already solved in (3).
(6) And so on, the idea being that we can first remove all the trees, by using the argument in (5), and then we are left with some sort of agglomeration of [math]N[/math]-gons, for which we can check the Euler formula directly, a bit as in (3), or by recurrence.
(7) To be more precise, let us try to do the recurrence on the number of faces [math]f[/math]. For this purpose, consider one of the faces of our graph, which looks as follows, with [math]v_i[/math] denoting the number of vertices on each side, with the endpoints excluded:
(8) Now let us collapse this chosen face to a single point, in the obvious way. In this process, the total number of vertices [math]v[/math], edges [math]e[/math], and faces [math]f[/math], evolves as follows:
Thus, in this process, the Euler quantity [math]v-e+f[/math] evolves as follows:
So, done with the recurrence, and the Euler formula is proved.
As a famous application, or rather version, of the Euler formula, let us record:
For a convex polyhedron we have the Euler formula
This is more or less the same thing as Theorem 7.7, save for getting rid of the internal trees of the planar graph there, the idea being as follows:
(1) In one sense, consider a convex polyhedron [math]P[/math]. We can then enlarge one face, as much as needed, and then smash our polyhedron with a big hammer, as to get a planar graph [math]X[/math]. As an illustration, here is how this method works, for a cube:
But, in this process, each of the numbers [math]v,e,f[/math] stays the same, so we get the Euler formula for [math]P[/math], as a consequence of the Euler formula for [math]X[/math], from Theorem 7.7.
(2) Conversely, consider a connected planar graph [math]X[/math]. Then, save for getting rid of the internal trees, as explained in the proof of Theorem 7.7, we can assume that we are dealing with an agglomeration of [math]N[/math]-gons, again as explained in the proof of Theorem 7.7. But now, we can inflate our graph as to obtain a convex polyhedron [math]P[/math], as follows:
Again, in this process, each of the numbers [math]v,e,f[/math] will stay the same, and so we get the Euler formula for [math]X[/math], as a consequence of the Euler formula for [math]P[/math].
Summarizing, Euler formula understood, but as a matter of making sure that we didn't mess up anything with our mathematics, let us do some direct checks as well:
The Euler formula [math]v-e+f=2[/math] holds indeed for the five possible regular polyhedra, as follows:
- Tetrahedron: [math]4-6+4=2[/math].
- Cube: [math]8-12+6=2[/math].
- Octahedron: [math]6-12+8=2[/math].
- Dodecahedron: [math]20-30+12=2[/math].
- Isocahedron: [math]12-30+20=2[/math].
The figures in the statement are certainly the good ones for the tetrahedron and the cube. Regarding now the octahedron, again the figures are the good ones, by thinking in 3D, but as an interesting exercise for us, which is illustrating for the above, let us attempt to find a nice way of drawing the corresponding graph:
(1) To start with, the “smashing” method from the proof of Proposition 7.8 provides us with a graph which is certainly planar, but which, even worse than before for the cube, sort of misses the whole point with the 3D octahedron, its symmetries, and so on:
(2) Much nicer, instead, is the following picture, which still basically misses the 3D beauty of the octahedron, but at least reveals some of its symmetries:
In short, you get the point, quite subjective all this, and as a conclusion, drawing graphs in an appropriate way remains an art. As for the dodecahedron and isocahedron, exercise here for you, and if failing, take some drawing classes. Math is not everything.
The Euler formula [math]v-e+f=2[/math], in both its above formulations, the graph one from Theorem 7.7, and the polyhedron one from Proposition 7.8, is something very interesting, at the origin of modern pure mathematics, and having countless other versions and generalizations. We will be back to it on several occasions, in what follows.
As a third main result now about the planar graphs, we have:
Any planar graph has the following properties:
- It is vertex [math]4[/math]-colorable.
- It is a [math]4[/math]-partite graph.
Heavy theorem that we have here, with our comments being as follows:
(1) This is something that we talked about in chapter 1, by calling there “maps” the planar graphs, and with the comment that the proof is something extremely complicated. So, you might perhaps expect, with our graph learning doing quite well, that we might have some new things to say, about this. Unfortunately, no, this is definitely very difficult, beyond our reach, but do not hesitate to look it up, and learn more about it.
(2) This being said, there are a few elementary things that we can do. First is the observation that 3 colors will not do, and that not all planar graphs are tripartite, and exercise here for you, to find some counterexamples. Also, it is possible to say of few other things, of theoretical nature, providing some evidence for the theorem, as stated.
(3) To be more precise, the fact that 3 colors will not do is clear for a flattened tetrahedron, and with the 4-coloring here [math]ABCD[/math] being, of course, as follows:
There are of course many things that can be said, along these lines.
As a conclusion to all this, planar graphs and related topics, as you can see from the above, the theory of planar graphs can vary a lot, with:
(1) Theorem 7.5 being something quite tricky.
(2) Theorem 7.7 being something rather deep and trivial.
(3) Theorem 7.10 being something of extreme difficulty.
Quite fascinating all this, hope you agree with me. In short, beware of planar graphs, you never know when coming across something trivial, or extremely complicated.
7c. Some topology
Switching topics now, let us get into the following question, which puts under the spotlight the graphs that we neglected so far, in this chapter: \begin{question} What are the graphs which are not planar, but can be however drawn on a torus? Also, what about graphs which can be drawn on higher surfaces, having [math]g\geq2[/math] holes, instead of the [math]g=0[/math] holes of the sphere, and the [math]g=1[/math] hole of the torus? \end{question} All this looks quite interesting, but before going head-first into such questions, let us pause our study of graphs, and look instead at surfaces, and other manifolds. The same questions make sense here, does our manifold have holes, and how many holes, of which type, and so on. Let us start with something that we know well, namely:
A topological space [math]X[/math] is called path connected when any two points [math]x,y\in X[/math] can be connected by a path. That is, given any two points [math]x,y\in X[/math], we can find a continuous function [math]f:[0,1]\to X[/math] such that [math]f(0)=x[/math] and [math]f(1)=y[/math].
The problem is now, given a connected space [math]X[/math], how to count its “holes”. And this is quite subtle problem, because as examples of such spaces we have:
(1) The sphere, the donut, the double-holed donut, the triple-holed donut, and so on. These spaces are quite simple, and intuition suggests to declare that the number of holes of the [math]N[/math]-holed donut is, and you guessed right, [math]N[/math].
(2) However, we have as well as example the empty sphere, I mean just the crust of the sphere, and while this obviously falls into the class of “one-holed spaces”, this is not the same thing as a donut, its hole being of different nature.
(3) As another example, consider again the sphere, but this time with two tunnels drilled into it, in the shape of a cross. Whether that missing cross should account for 1 hole, or for 2 holes, or for something in between, I will leave it up to you.
Summarizing, things are quite tricky, suggesting that the “number of holes” of a topological space [math]X[/math] is not an actual number, but rather something more complicated. Now with this in mind, let us formulate the following definition:
The homotopy group [math]\pi_1(X)[/math] of a connected space [math]X[/math] is the group of loops based at a given point [math]*\in X[/math], with the following conventions,
- Two such loops are identified when one can pass continuously from one loop to the other, via a family of loops indexed by [math]t\in[0,1][/math],
- The composition of two such loops is the obvious one, namely is the loop obtained by following the first loop, then the second loop,
- The unit loop is the null loop at [math]*[/math], which stays there, and the inverse of a given loop is the loop itself, followed backwards,
with the remark that the group [math]\pi_1(X)[/math] defined in this way does not depend on the choice of the given point [math]*\in X[/math], where the loops are based.
This definition is obviously something non-trivial, based on some preliminary thinking on the subject, the technical details being as follows:
-- The fact that the set [math]\pi_1(X)[/math] defined as above is indeed a group is obvious, with all the group axioms being clear from definitions.
-- Obvious as well is the fact that, since [math]X[/math] is assumed to be connected, this group does not depend on the choice of the given point [math]*\in X[/math], where the loops are based.
As basic examples now, for spaces having “no holes”, such as [math]\mathbb R[/math] itself, or [math]\mathbb R^N[/math], and so on, we have [math]\pi_1=\{1\}[/math]. In fact, having no holes can only mean, by definition, [math]\pi_1=\{1\}[/math]:
A space is called simply connected when:
So, this will be our starting definition, for the considerations in this section. As further illustrations for Definition 7.13, here are now a few basic computations:
We have the following computations of homotopy groups:
- For the circle, we have [math]\pi_1=\mathbb Z[/math].
- For the torus, we have [math]\pi_1=\mathbb Z\times\mathbb Z[/math].
- For the disk minus [math]2[/math] points, we have [math]\pi_1=F_2[/math].
- In fact, for the disk minus [math]N[/math] points, we have [math]\pi_1=F_N[/math].
These results are all standard, as follows:
(1) The first assertion is clear, because a loop on the circle must wind [math]n\in\mathbb Z[/math] times around the center, and this parameter [math]n\in\mathbb Z[/math] uniquely determines the loop, up to the identification in Definition 7.13. Thus, the homotopy group of the circle is the group of such parameters [math]n\in\mathbb Z[/math], which is of course the group [math]\mathbb Z[/math] itself.
(2) In what regards now the second assertion, the torus being a product of two circles, we are led to the conclusion that its homotopy group must be some kind of product of [math]\mathbb Z[/math] with itself. But pictures show that the two standard generators of [math]\mathbb Z[/math], and so the two copies of [math]\mathbb Z[/math] themselves, commute, [math]gh=hg[/math], so we obtain the product of [math]\mathbb Z[/math] with itself, subject to commutation, which is the usual product [math]\mathbb Z\times\mathbb Z[/math]:
It is actually instructive here to work out explicitly the proof of the commutation relation. We can use our usual drawing conventions for the torus, namely:
The standard generators [math]g,h[/math] of the homotopy group are then as follows:
Regarding now the two compositions [math]gh,hg[/math], these are as follows:
But these two pictures coincide, up to homotopy, with the following picture:
Thus we have indeed [math]gh=hg[/math], as desired, which gives the formula in (2).
(3) Regarding now the disk minus [math]2[/math] points, the result here is quite clear, because the homotopy group is generated by the 2 loops around the 2 missing points, and these 2 loops are obviously free, algebrically speaking. Thus, we obtain a free product of the group [math]\mathbb Z[/math] with itself, which is by definition the free group on 2 generators [math]F_2[/math].
(4) This is again clear, because the homotopy group is generated here by the [math]N[/math] loops around the [math]N[/math] missing points, which are free, algebrically speaking. Thus, we obtain a [math]N[/math]-fold free product of [math]\mathbb Z[/math] with itself, which is the free group on [math]N[/math] generators [math]F_N[/math].
We will be back to more such computations in chapter 8 below.
There are many other interesting things that can be said about homotopy groups. Also, another thing that can be done with the arbitrary topological spaces [math]X[/math], again in relation with studying their “shape”, is that of looking at the fiber bundles over them, again up to continuous deformation. We are led in this way into a group, called [math]K_0(X)[/math]. Moreover, both [math]\pi_1(X)[/math] and [math]K_0(X)[/math] have higher analogues [math]\pi_n(X)[/math] and [math]K_n(X)[/math] as well, and the general goal of algebraic topology is that of understanding all these groups, along with some other groups, of similar flavor, which can be constructed as well.
Moving ahead with some further topology, we have:
\begin{fact} We can talk about the genus of a surface
as being its number of holes. \end{fact} To be more precise here, the genus of a sphere is by definition 0, then the genus of a torus is 1, then the genus of a doubly holed torus is 2, and so on.
At this point, I am sure that you are wondering what the genus exactly is, mathematically speaking. There are many answers here, ranging from elementary to advanced, depending on how much geometric you want to be, and the best answer, which is a bit complicated, involves complex analysis, and the notion of Riemann surface.
7d. Higher genus
Getting back to graphs, with the above understood, we can now formulate the following key result, coming as a continuation and generalization of Theorem 7.7:
For a connected graph of genus [math]g\in\mathbb N[/math] we have the Euler formula
This is something quite straightforward, as follows:
(1) This comes as a continuation of Theorem 7.7, dealing with the case [math]g=0[/math], and assuming that you have worked out all the details of the proof there, you will certainly have no troubles now in understanding the present extension, to genus [math]g\in\mathbb N[/math].
(2) So, instead of further insisting on the proof, which is something straightforward, let us see some illustrations, in genus [math]g\geq1[/math]. Our simplest example of non-planar graph is the simplex [math]K_5[/math], and we have seen how to draw this graph on a torus, showing that the genus is [math]g=1[/math]. But the picture that we used can now be recycled, in order to count the faces of [math]K_5[/math], when drawn on a torus, and there are 5 faces, as follows:
To be more precise, we have the four obvious faces [math]1,2,3,4[/math], and then everything else is in fact a single face 5, because by moving left and right, and up and down, according to our gluing conventions for the torus, we can travel from everywhere to everywhere, by avoiding that two edges, represented by dotted lines. Thus, we have 5 faces indeed, and as a conclusion to this, the Euler formula holds indeed for [math]K_5[/math], as:
(3) A similar discussion goes for the bipartite simplex [math]K_{3,3}[/math], with this graph being drawable on a torus, with 3 faces, as follows, with our various conventions above:
Thus, again as good news, the Euler formula holds indeed for [math]K_{3,3}[/math], as:
(4) Regarding now the higher simplices [math]K_N[/math] and bipartite simplices [math]K_{M,N}[/math], things here are quite complicated, as already discussed in Theorem 7.4. To be more precise, in what regards the simplices, we know that [math]K_3,K_4[/math] have genus [math]g=0[/math], then [math]K_5,K_6,K_7[/math] have genus [math]g=1[/math], and then [math]K_8[/math] has genus [math]g=2[/math], and in all cases the Euler formula holds, as:
In general, the verification of the Euler formula for the simplex [math]K_N[/math] is something quite complicated, which takes the following form, with [math]f[/math] being the number of faces, with this coming from the general genus formula mentioned in the proof of Theorem 7.4:
(5) As for the general bipartite simplices, [math]K_{M,N}[/math] with [math]M\leq N[/math], the situation here is quite similar. To start with, at [math]M=2[/math] these graphs are planar, as explained in the proof of Proposition 7.3, and the picture there shows that the Euler formula for them reads:
At [math]M\geq3[/math] these graphs are no longer planar, and here are a few numerics for them, namely Euler formula, with input coming from Theorem 7.4:
In general, the Euler formula holds indeed for [math]K_{M,N}[/math], in the following form, coming from the general genus formula mentioned in the proof of Theorem 7.4:
(6) Summarizing, quite non-trivial all this, concrete applications of the Euler formula, and exercise of course for you, to learn more about such things.
As another application of the notion of genus, and of the Euler formula, let us discuss now the Petersen graph. We have the following result, about it:
The Petersen graph, namely
There are several things going on here, the idea being as follows:
(1) The fact that this graph is indeed not planar can be best seen by using the Wagner criterion from Theorem 7.5, with both the graphs [math]K_5[/math] and [math]K_{3,3}[/math] being minors of it, and we have already talked about this, with full details, in Proposition 7.6.
(2) Regarding now the toral graph assertion, this requires some skill. By inverting the two pentagons, in the obvious way, the Petersen graph becomes as follows:
But now, we can keep the two pentagons and the solid edges, and send flying the various dotted edges, on suitable directions on a torus, as follows:
Observe the usage of the lower left vertex, which is identified with the upper right vertex, and in fact with the other two vertices of the rectangle as well, according to our gluing conventions for the torus. In any case, job done, and torality proved.
(3) In order to finish, we still have to count the number of faces, in order to check the Euler formula. But there are 5 faces, as shown by the following picture:
Thus the Euler formula holds indeed in our embedding, as [math]10-15+5=0[/math].
Many other things can be said about the Petersen graph, and other toral graphs, of similar type, or of general type. Exercise of course, read a bit here, if interested.
General references
Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].