Let \(\delta\) denote the minimum degree of a vertex in a graph. For all…
2014
Let \(\delta\) denote the minimum degree of a vertex in a graph. For all planar graphs on \(n\) vertices with \(\delta \geq 3\), which one of the following is TRUE?
Answer: A. In any planar embedding, the number of faces is at least \(\frac{n}{2}+2\) — Key insight: combine the handshake lemma with Euler's formula. Step 1: Sum of degrees ≥ 3n, so 2m ≥ 3n and therefore m ≥ 3n/2. Step 2: Euler's formula for a…
- A.
In any planar embedding, the number of faces is at least
\(\frac{n}{2}+2\) - B.
In any planar embedding, the number of faces is less than
\(\frac{n}{2}+2\) - C.
There is a planar embedding in which the number of faces is less than
\(\frac{n}{2}+2\) - D.
There is a planar embedding in which the number of faces is at most
\(\frac {n}{\delta+1}\)
Attempted by 143 students.
Show answer & explanation
Correct answer: A
Key insight: combine the handshake lemma with Euler's formula.
Step 1: Sum of degrees ≥ 3n, so 2m ≥ 3n and therefore m ≥ 3n/2.
Step 2: Euler's formula for a planar drawing with c components is n − m + f = 1 + c. In particular (for at least one component) f = m − n + 2, and in general f = m − n + 1 + c ≥ m − n + 2.
Step 3: Combine the two inequalities: f ≥ 3n/2 − n + 2 = n/2 + 2. Thus every planar embedding has at least n/2 + 2 faces.
Remark: Equality occurs when every vertex has degree 3 and the graph is connected (for example K4), so the bound is tight in such cases.
Explore the full course: Iocl Engineers Officers Grade A Paper 2