Teaching MPPSC Assistant Professor Mock Test Series 2025 Engineering Mathematics Graph Theory Planarity
Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is TRUE?
1
In any planar embedding, the number of faces is at least \(\frac{n}{2} + 2\)
2
In any planar embedding, the number of faces is less than \(\frac{n}{2} + 2\)
3
There is a planar embedding in which the number of faces is less than \(\frac{n}{2} + 2\)
4
There is a planar embedding in which the number of faces is at most \(\frac{n}{{\delta + 1}}\)