Planar graphs and Euler’s formula (intro) - Discrete Math

1. In a simple connected planar graph, if every face is bounded by at least $k$ edges and every edge bounds exactly $2$ faces, which inequality must hold between the number of edges $e$ and faces $f$?
   Answer: $kf \leq 2e$ When you encounter planar graph problems involving faces and edges, you're working with fundamental counting relationships that connect the geometric structure to algebraic inequalities. The key insight is understanding what "every face is bounded by at least $k$ edges" means for counting. If you count all edge-face incidences by going around each face, you get at least $kf$ total incidences (since each of the $f$ faces contributes at least $k$ edges to this count). However, when you count the same incidences by considering each edge, you get exactly $2e$ incidences, because every edge bounds exactly 2 faces. Since you're counting the same thing two ways, the constraint "at least $k$ edges per face" gives you $kf \leq 2e$. Answer A ($kf = 2e$) would only hold if every face has exactly $k$ edges, but the problem states "at least $k$" edges. Answer B ($kf \geq 2e$) reverses the inequality direction—this would imply that counting by faces gives more incidences than counting by edges, which is impossible since faces can only have at least $k$ edges, not fewer. Answer D ($2f \leq ke$) rearranges terms incorrectly and doesn't follow from the given constraints. The correct answer is C: $kf \leq 2e$. Study tip: In planar graph problems, always use double counting—count the same quantity (like edge-face incidences) in two different ways, then apply the given constraints to establish inequalities.
2. Consider a connected planar graph where removing any single edge would increase the number of faces by exactly 1. If the graph has 8 vertices and 12 edges, how many faces does it have?
   Answer: 6 The condition that removing any edge increases the number of faces by exactly 1 means that every edge lies on the boundary between two distinct faces (i.e., no edge is a bridge and no edge bounds the same face on both sides). Using Euler's formula: $V - E + F = 2$ with $V = 8$ and $E = 12$: $8 - 12 + F = 2$, so $F = 6$.
3. In analyzing a connected planar graph, you find that it has $7$ faces (including the outer face) and $11$ edges. If you add one new vertex by subdividing an existing edge, what will be the number of faces in the resulting graph?
   Answer: $7$ When subdividing an edge, we add one vertex and one edge (the original edge becomes two edges). Original: $v - 11 + 7 = 2$, so $v = 6$. After subdivision: $v' = 7$, $e' = 12$. By Euler's formula: $f' = 2 - v' + e' = 2 - 7 + 12 = 7$. The number of faces doesn't change because no new face is created. Choice B assumes one new face is added. Choice C subtracts a face incorrectly. Choice D assumes two new faces are added.
4. Consider a connected planar graph where every face (including the outer face) is bounded by exactly 4 edges. If the graph has 10 faces, how many edges does it have?
   Answer: 20 If every face is bounded by 4 edges, then counting face-edge incidences gives $4F = 2E$ (each edge borders exactly 2 faces). With $F = 10$, we get $4(10) = 2E$, so $E = 20$. We can verify this is consistent with Euler's formula: $V - E + F = 2$ gives $V - 20 + 10 = 2$, so $V = 12$.
5. A simple connected planar graph has $12$ vertices, and each vertex has degree $3$. If this graph is drawn in the plane without edge crossings, how many faces does it have?
   Answer: $8$ First find the number of edges: since each vertex has degree 3, the sum of degrees is $12 \times 3 = 36$. By the handshaking lemma, $2e = 36$, so $e = 18$. Using Euler's formula: $v - e + f = 2$ gives $12 - 18 + f = 2$, so $f = 8$. Choice A forgets the outer face. Choice C uses $e = 15$ incorrectly. Choice D uses $e = 21$ incorrectly.
6. A connected planar graph has 12 vertices and 18 edges. When drawn in the plane without edge crossings, what is the minimum number of faces (including the outer face) that this graph must have?
   Answer: 8 Using Euler's formula for connected planar graphs: $V - E + F = 2$. With $V = 12$ and $E = 18$, we get $12 - 18 + F = 2$, so $F = 8$. This is both the minimum and exact number of faces for any planar embedding of this graph.
7. In a connected planar graph, the sum of the degrees of all faces is 20. If the graph has 7 vertices, how many edges does it have?
   Answer: 10 The sum of the degrees of all faces equals $2E$ (since each edge is counted twice when summing face degrees). Given that this sum is 20, we have $2E = 20$, so $E = 10$. We can verify using Euler's formula: $V - E + F = 2$ gives $7 - 10 + F = 2$, so $F = 5$.
8. A wheel graph $W_n$ consists of a cycle $C_n$ plus one central vertex connected to all vertices of the cycle. For $W_7$ (wheel with $7$-cycle), how many faces does the planar embedding have?
   Answer: $8$ When working with planar graphs, you'll often need to count faces using Euler's formula: $V - E + F = 2$, where $V$ is vertices, $E$ is edges, and $F$ is faces (including the outer face). For wheel graph $W_7$, let's identify the components. You have a 7-cycle $C_7$ with 7 vertices, plus one central vertex connected to all cycle vertices. This gives you $V = 7 + 1 = 8$ vertices total. For edges, count systematically: the 7-cycle contributes 7 edges, and the central vertex connects to each of the 7 cycle vertices, adding 7 more edges. So $E = 7 + 7 = 14$ edges. Using Euler's formula: $8 - 14 + F = 2$, which gives $F = 8$ faces. You can visualize this: the central vertex and its spokes divide the interior of the 7-cycle into 7 triangular faces, plus there's always the outer (unbounded) face, totaling 8 faces. Looking at the wrong answers: (A) 7 likely counts only the triangular faces while forgetting the outer face. (B) 9 might come from incorrectly adding an extra face or miscounting edges. (D) 10 could result from errors in applying Euler's formula or double-counting some structural elements. Study tip: For wheel graphs $W_n$, remember the pattern: you get $n$ triangular faces plus 1 outer face, totaling $n + 1$ faces. This direct counting often provides a good check against Euler's formula calculations.
9. A simple connected planar graph has the property that every vertex has degree at least $3$. If the graph has $n$ vertices, what is the minimum number of faces it must have?
   Answer: $\frac{n}{2} + 2$ Since each vertex has degree at least 3, we have $2e \geq 3n$, so $e \geq \frac{3n}{2}$. From Euler's formula: $f = 2 - n + e \geq 2 - n + \frac{3n}{2} = 2 + \frac{n}{2} = \frac{n}{2} + 2$. Choice B rearranges this incorrectly. Choice C ignores the degree constraint. Choice D uses $f \geq \frac{3n}{2} - 2$ incorrectly.
10. If you remove one edge from a connected planar graph with $v$ vertices, $e$ edges, and $f$ faces, the resulting graph remains connected. What is the relationship between the number of faces in the new graph?
    Answer: The new graph has $f - 1$ faces This question tests your understanding of how face count changes when you modify the structure of a planar graph, which connects to Euler's formula for planar graphs: $v - e + f = 2$. When you remove an edge from a connected planar graph while keeping it connected, you're essentially eliminating a boundary between two faces. Think of it like removing a wall between two rooms in a house - the two separate rooms become one larger room. In graph theory terms, the two faces that were previously separated by that edge merge into a single face, reducing the total face count by exactly one. You can verify this using Euler's formula. In the original graph: $v - e + f = 2$. After removing one edge, you have $v$ vertices, $e-1$ edges, and the new number of faces must satisfy: $v - (e-1) + f_{new} = 2$. Solving for $f_{new}$: $f_{new} = 2 - v + e - 1 = (2 - v + e) - 1 = f - 1$. Choice A ($f-2$) would require removing two faces, which doesn't happen from a single edge removal. Choice B ($f$) incorrectly assumes edge removal doesn't affect face count - but edges are face boundaries, so removing them must change the face structure. Choice C ($f+1$) suggests adding a face, which contradicts the merging behavior when boundaries are removed. Remember: in planar graphs, edges serve as boundaries between faces. Removing an edge removes a boundary, causing adjacent faces to merge and reducing the total count by one.
11. A connected planar graph $G$ has $15$ vertices and $22$ edges. When drawn in the plane without edge crossings, what is the number of faces (including the outer face)?
    Answer: $9$ By Euler's formula for connected planar graphs: $v - e + f = 2$. Substituting $v = 15$ and $e = 22$: $15 - 22 + f = 2$, so $f = 9$. Choice A results from the error $15 - 22 + f = 1$. Choice C results from forgetting to count the outer face. Choice D results from the error $v + e - f = 2$.

Start this quiz