Faces
Task number: 3845
Consider only those drawings of planar graphs in which each face is bounded by a cycle and where different faces may have at most one edge in common. We do not consider graphs without edges.
In each such graph \( G \) we look for a suitable vertex \( u \) so that by removing it the number of faces will decrease as much as possible. What decrease can we always guarantee? If more than one option applies, select the highest one.
- 2
- 4
- 6
Solution
The smallest degree in the \( G \) graph is 3 – if it was smaller, some face is not bounded by a cycle (degree 1) or some faces have more edges in common (degree 2).
By removing the vertex of degree \( k \), the \( k \) faces are merged into one, ie the number of faces decreases by \( k-1 \).
In general, the existence of a vertex of higher degree cannot be guaranteed, see e.g. a drawing of \( K_4 \).
Answer
The correct answer is a.
