Given the null graph with no edges or vertices, we have a connected planar graph as no edges cross when this graph is drawn in the plane, and the fact that any two distinct vertices have a path between them is vacuously true. However, Euler's formula doesn't work: plugging into $v+f= e+2$, we have $1=2$. Why is this the case? Can we not apply Euler's formula here?
$\begingroup$
$\endgroup$
4
-
8$\begingroup$ It's not the only property the "null graph" breaks. I'd be in the camp of "graphs must have a nonempty vertex set". $\endgroup$– Brian MoehringAug 8 at 7:09
-
7$\begingroup$ Topologically speaking the Euler formula only holds if each open face of the embedding into $S^2$ is homeomorphic to an open disk (formally you need something like a CW-decomposition of $S^2$), and in your case this does not hold - the only "face" of the embedding of the empty graph into $S^2$ is $S^2$. You can as an exercise in algebraic topology try to formulate the appropriate fix to the formula. $\endgroup$– Michal AdamaszekAug 8 at 7:13
-
2$\begingroup$ One "fix" is that the faces are counted by their Euler characteristic. For most connected graphs, assuming we draw our graph on a sphere, all faces are topologically disks, and disks have Euler characteristic $1$. For a null graph, the unbounded face will be a sphere, which has Euler characteristic $2$. (For a disconnected graph, we can have faces that look like annuluses or punctured disks, which have $0$ or negative Euler characteristic.) $\endgroup$– Akiva WeinbergerAug 9 at 23:49
-
10$\begingroup$ @BrianMoehring I disagree, for what it's worth. I think that the null graph is fine, but that "connected" should be redefined to mean "exactly one connected component" instead of "at most one connected component". The latter notion is never useful, in my experience. $\endgroup$– Akiva WeinbergerAug 10 at 0:00
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
We can slightly generalize Euler's formula as: $V-E+F-C = 1$, where $C$ is the number of components. Most of the time $C=1$, which gives us the familiar formula. But it works great if $C>1$. And the question is about the "trivial" case where $C=0$. Now of course $V=E=0$ and $F=1$, giving us the right answer.
There is a standard inductive proof of Euler's formula which involves either removing an edge and a face, or removing an edge and a vertex, and observing that the invariant remains the same. See here. But these proofs are quite complicated, because they are trying to preserve connectedness.
With the generalized formula, the proof can be much cleaner (still skating over elementary topology). Remove any edge. There are two disjoint possibilities:
(1) We merge two distinct faces, so: $E-1; F-1$
(2) The edge always had the same face on both sides, so removing the edge instead splits a component into two: $E-1; C+1$
In either case the invariant $V-E+F-C$ remains the same. So we remove all the edges, and then have a bunch of isolated vertex/components in a single face, so $V=C$ and hence $V-0+1-C = 1$.
Always nice when a formula can apply all the way down to $0$.
-
$\begingroup$ I have suggested this because it is not clear to me that there always exists an isolated vertex to remove from a graph to prove this inductively in this manner $\endgroup$ Aug 8 at 18:59
-
1$\begingroup$ I think the proof should aim to retain the intuition. If we apply the first two reductions successively then we end up with a number of isolated vertices. There’s nowhere else to go. Then we can apply the third reduction to eliminate those. $\endgroup$– LaskaAug 8 at 20:23
-
3$\begingroup$ You can stop once all the edges are removed, as then each vertex is its own component, so $C = V, E = 0, F = 1$. $\endgroup$ Aug 9 at 14:28
-
1$\begingroup$ @PaulSinclair thanks - as you maybe saw I followed your suggestion $\endgroup$– LaskaAug 9 at 14:58
-
2$\begingroup$ Yes I had. I had mentioned it because this is my favorite proof of Euclid's formula too. $\endgroup$ Aug 9 at 15:00