Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 1 down vote accepted

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$.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.