Euler's Formula for Planar Graphs
Euler's formula is the central counting relation for planar graphs. It connects vertices, edges, connected components, and regions even though the drawing may look complicated.
For a connected planar embedding,
where includes the unbounded outer face.
A planar graph is already drawn with no edge crossings. We know its number of vertices , edges , and connected components . Find the number of faces, including the outer face.
For a graph with several components, the correct formula is
Therefore .
Start with isolated vertices. There is only one face: the whole plane.
Now add edges one at a time:
In both cases, stays equal to . This gives the generalized formula.
The graph must be considered as an embedding. If two drawn edges cross, their intersection must be turned into a vertex and both edges must be split before applying the formula.
Once , , and are known, no traversal is needed.
Algorithm:
If only bounded regions are requested, print .
The face count changes only when a new edge closes a cycle. Watch four vertices become a connected tree, then gain one bounded region.
The input contains , , and for a valid planar embedding.
1. Read V, E, and C.
2. Calculate F = E - V + C + 1.
3. Print F.
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
void solve() {
long long v, e, c;
cin >> v >> e >> c;
long long faces = e - v + c + 1;
cout << faces << '\n';
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}