Faces and Euler's formula

Which method is valid for a connected planar graph?

Euler's formula

For a connected planar graph, the number of vertices plus the number of faces is two more than the number of edges. The face count includes the infinite outer face

1. 1Check the conditions Use this identity only when the graph is connected and planar \(\displaystyle \text{connected and planar}\;\Rightarrow\;v+f=e+2\)
2. 2Substitute known counts Replace the known vertex, edge or face counts in the identity \(\displaystyle v=6,\;e=9\;\Rightarrow\;6+f=9+2\)
3. 3Solve the missing count Rearrange the equation after substitution \(\displaystyle 6+f=11\;\Rightarrow\;f=5\)
4. 4Include the outer face The infinite region outside the drawing is one of the faces \(\displaystyle 4\text{ enclosed regions}+1\text{ outer region}=5\text{ faces}\)

For a connected planar graph with 9 edges, calculate the value of e + 2.

A connected planar graph has 6 vertices and e + 2 = 11. Use Euler's formula to find the number of faces

Putting 2 on the wrong side. One of these lines is right. Which one?

Faces belong to a plane drawing

A face is a connected region of the plane outside the drawing. Include the one unbounded outer region. An edge is not a face, and a graph drawn with crossings is not a plane embedding from which to count faces

This is a fixed crossing-free square with diagonal AC. How many faces does this embedding have, including the outside?

Delete a cycle edge, not a bridge

In a connected plane graph, choose an edge on a cycle. The rest of that cycle still connects its endpoints, so deleting the edge keeps the graph connected. Its two sides lie in distinct faces, which merge into one when the edge is removed. The vertex count stays fixed; the edge and face counts each decrease by one

A plane graph has edges AB, BC, CA and CD. Which deletion is valid for the cycle-edge reduction?

The invariant and the stopping point

Deleting a cycle edge leaves v − e + f unchanged. Repeat only while a cycle remains. The number of edges is finite and strictly decreases, so the process stops. The graph is still connected and now acyclic: it is a tree on the same v vertices. A plane tree has v − 1 edges and only one face, including the one-vertex tree

Prove Euler’s formula, ungraded

For a finite simple connected planar graph, write a complete proof that v − e + f = 2. Begin with a crossing-free embedding. Justify the cycle-edge deletion, preservation of connectedness, change in face count, termination and tree value. Full proof construction is ungraded

Model: Euler’s formula by reduction

Choose a plane embedding of the given graph. If it has a cycle, delete one cycle edge. Its endpoints remain connected along the rest of the cycle, and its two distinct incident faces merge; hence e and f both fall by one while v stays fixed. Thus v − e + f is unchanged. Repeat until no cycle remains. Finiteness makes this terminate, and connectedness has been preserved, so the remaining graph is a tree. Section 2B gives e = v − 1 for a tree, and a plane tree has f = 1 because it encloses no region. Its value is v − (v − 1) + 1 = 2. The unchanged value in the original embedding is therefore also 2.

A connected simple planar graph has 8 vertices, each of degree 3. How many faces does a plane embedding have?

Disconnected graphs need a different constant

Two disjoint triangles have six vertices and six edges. Their usual separate plane drawing has two bounded faces and one common outer face, so v − e + f = 3, not 2. More generally a plane graph with c components satisfies v − e + f = 1 + c. The connected formula is the c = 1 case; do not silently apply it to a disconnected graph

A bound for simple planar graphs

For a connected simple plane graph with v at least 3, each face boundary walk has at least three edge occurrences. Count boundary occurrences, not just distinct edges: a bridge is counted twice along the same face. Every edge contributes two sides, so 3f ≤ 2e. Combining this with f = 2 − v + e gives 3(2 − v + e) ≤ 2e, hence e ≤ 3v − 6. This is a necessary condition, not a general planarity test

K5 has five vertices and ten edges. What follows from the simple planar bound?

The stronger bipartite bound

A bipartite graph has no odd cycle, so a connected simple bipartite plane graph with v at least 3 has face boundary walks of length at least four. Bridges still contribute twice. Thus 4f ≤ 2e. With Euler’s formula this gives e ≤ 2v − 4 for a connected simple bipartite planar graph. The three-vertex path has one face with four boundary occurrences, so the bridge convention matters

K3,3 is simple, connected and bipartite, with six vertices and nine edges. Which conclusion is justified?