# Question about Euler's polyhedral formula in a proof of minimum distances

I am confused by a step made in a proof of the following result.

Let $f_{2}^{\text{min}}(n)$ denote the maximum number of times the minimum distance can occur among n points in the plane. Then $f_{2}^{\text{min}}(n) = \lfloor 3n - \sqrt{12n-3} \rfloor$.

Proof: Assume $n \geq 3$ and consider a set $P$ of $n$ points with minimum distance 1, and connect two elements of $P$ by a segment if and only if their distance is exactly 1. Thus, we obtain a graph $G$ embedded in the plane. Assume that $G$ has the largest possible number of edges; that is, $|E(G)|=f_{2}^{\text{min}}(n)$. It is easy to see that every vertex of $G$ is adjacent to at least two other vertices. Moreover, $G$ is two-connected; that is, $G$ remains connected after the removal of any of its vertices. The outer face of $G$ is bounded by a simple closed polygon $C$. Let $b$ and $b_{d}$ denote the total number of vertices of this polygon and the number of those vertices that have degree $d$ in $G$, respsectively. Clearly, $b = b_{2} + b_{3} + b_{4} + b_{5}$. The internal angle of $C$ at a vertex of degree $d$ is at least $(d-1)\frac{\pi}{3}$, and the sum of these angles is $(b-2)\pi$. Hence, $b_{2} + 2b_{3} + 3b_{4} + 4b_{5} \leq 3b-6$. [Important Part]:

On the other hand, denoting by $f_{i} (i \geq 3)$ the number of internal faces of $G$ with $i$ sides, we obtain from Euler's polyhedral formula that, $$n - f_{2}^{\text{min}}(n) + f_{3} + f_{4} + ... = 1$$

The proof then continues and I understand everything before and after where it is mentioned that $n - f_{2}^{\text{min}}(n) + f_{3} + f_{4} + ... = 1$, but how is this arrived at? It is likely a very very simple answer, but if you could explain with details how this is arrived at by Euler's polyhedral formula I would be able to understand the proof. Thank you.

EDIT: I'm concerned with either my understanding that $V - E + F = 2$ for any graph embedding or convex polyhedra, or Gerry Myerson's answer that the Euler characteristic should be 1? Can anyone else comment on this?

-
 In the displayed formula, there is a term, $f(n)$, that has not been defined. – Gerry Myerson May 7 '12 at 7:03

Euler's formula is $$n-e+f=1$$ where $n$ is the number of vertices, $e$ the number of edges, and $f$ the number of faces (not counting the "outside" face). In turn, $$f=f_3+f_4+\dots$$ just counting the faces by the number of sides, since every face has at least 3 sides.
EDIT: If I understand the comments and the edit by OP, the entire question is why there's a $1$ on the right side of the formula instead of a $2$. As I explain in my comments, $$n-e+f=2$$ works for embeddings in a sphere, but it looks like the source OP is quoting is doing the embedding in a plane, and is not counting the outside region; under those circumstances, you "lose" one face, and that's why there's a $1$ on the right instead of a $2$.
 Where does the $1$ come from? I don't know how to prove that the $\chi = 1$, where $\chi$ is the Euler characteristic of $G$. – Samuel Reid May 7 '12 at 7:16 Every graph embedded (without edge-crossings) in the plane has the same Euler characteristic, namely, 1; that's exactly what Euler's formula (for polyhedra, interpreted as a theorem about their planar realizations) tells you. – Gerry Myerson May 7 '12 at 12:53 Isn't the Euler characterstic equal to 2 for graph embeddings? – Samuel Reid May 7 '12 at 14:53 When a graph is embedded in the sphere, the Euler characteristic is 2. When it's embedded in the plane (and when, as I explicitly noted in my answer, you don't count the outside face), the formula takes a 1 instead of a 2. Try it! Draw some (polyhedral) graph in the plane, count vertices, edges, and faces (not counting the outside face), and compute $v-e+f$; I bet you get 1. When you use the formula on a polyhedron, you are embedding in a sphere, there is no such thing as an outside face, and the formula needs a 2. – Gerry Myerson May 8 '12 at 3:38 Thank you! That really clarifies my confusion about "the infinite outside face", etc. I appreciate the response. – Samuel Reid May 9 '12 at 2:00