4
$\begingroup$

How does a graph with one vertex have one face? I understand Euler's theorem polyhedron $V-E+F=2$. However, I don't understand what a polytope and hyperplane is so I can't understand the topologically complicated definition of face. If I lookup a dumbed-down version of what a "face" is, it's too hand-wavy.

Let's say I have the following graph with $6$ vertices, $6$ edges, and therefore $2$ faces. I see how the triangular-like region formed by $4$ vertices makes up a face. I however don't understand how the extra 1 face was counted. See image drawn below:

enter image description here

Next, let's remove an edge below. Now the transformed graph below has $1$ face total. How the heck did this happen? How does it have $1$ face and not $2$?

See below:

enter image description here

Recall wolfram's:

Generally, a face is a component polygon, polyhedron, or polytope. A two-dimensional face thus has vertices and edges, and can be used to make cells. More formally, a face is the intersection of an $n$-dimensional polytope with a tangent hyperplane. Zero-dimensional faces are known as polyhedron vertices (nodes), one-dimensional faces as polyhedron edges, $(n-2)-D$ faces as ridges, and $(n-1)$-dimensional faces as facets.

and the "Face" in dumbed-down speak

 is regions bounded by edges, including the outer, infinitely large region

What infinitely large region does wikipedia talk about on https://en.wikipedia.org/wiki/Planar_graph? Is every graph bounded by an infinitely larger graph? Does that mean that an infinitely large graph is a non-existent because it is an element and subset of itself and therefore not an element of itself? Russell's paradox

$\endgroup$
  • $\begingroup$ Isn't a face something of the form $\overline C$ where $C$ is a connected component of $\mathbb R^2$ minus the embedding? $\endgroup$ – Jorge Fernández Hidalgo Jun 11 '17 at 3:58
  • $\begingroup$ Your second image has two faces. Note that the graph has 5 vertices and 5 edges, giving equality for $(5) - (5) + F = 2$. Also, the "infinitely large region" Wikipedia mentions in the region "surrounding" the graph. $\endgroup$ – Santana Afton Jun 11 '17 at 4:06
  • $\begingroup$ The second image has 6 vertices. I removed one edge without removing the endpoints of the edge. $\endgroup$ – user420360 Jun 11 '17 at 4:09
  • $\begingroup$ I can remove an edge without removing endpoints. that smudge is a vertex. 6-(6-1)+x=2. x=1=faces. $\endgroup$ – user420360 Jun 11 '17 at 4:09
  • 2
    $\begingroup$ Ah, I see what you mean. Euler's Formula only applies to connected graphs. If we try to apply it to non-connected graphs, we have the situation where a group of $n$ vertices with no edges would imply there exist $2 - n$ faces, and we would have to make sense of "negative" faces. $\endgroup$ – Santana Afton Jun 11 '17 at 4:12
9
$\begingroup$

In your second image, the floating disconnected vertex is throwing off your total. Euler's Theorem only applies to connected graphs -- otherwise you could arbitrarily add as many isolated vertices as you want and make $F-E+V$ come out to any arbitrary whole number greater than or equal to $2$.

$\endgroup$
5
$\begingroup$

The last face is the entire plane that isn’t in the other faces you mentioned, which they called the outer, infinitely large region. In the case of a single point, it is the entire plane. A face can be thought of as a region of space such that you ca go anywhere in the region without having to cross over a line. Also, Euler's Theorem only applies to connected graphs.

Planar cube

As an example, here is a planar graph representing a cube. You'll notice that the left image tells you to remove the bottom, but it should say that the area that isn’t labeled "side" or "top" is the bottom of the cube.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy