Discrete Math Quiz: Planar Graphs And Eulers Formula
11 questions · exam conditions
0:00
Planar Graphs And Eulers FormulaQuestion 1 of 11

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?

5
6
7
8
← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Planar Graphs And Eulers Formula

Practice Planar Graphs And Eulers Formula in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Planar Graphs And Eulers Formula, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

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?

  1. 5
  2. 6 (correct answer)
  3. 7
  4. 8
Explanation: 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=2V - E + F = 2 with V=8V = 8 and E=12E = 12: 8−12+F=28 - 12 + F = 2, so F=6F = 6.

Question 2

In a simple connected planar graph, if every face is bounded by at least kk edges and every edge bounds exactly 22 faces, which inequality must hold between the number of edges ee and faces ff?

  1. kf=2ekf = 2e
  2. kf≥2ekf \geq 2e
  3. kf≤2ekf \leq 2e (correct answer)
  4. 2f≤ke2f \leq ke
Explanation: 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 kk edges" means for counting. If you count all edge-face incidences by going around each face, you get at least kfkf total incidences (since each of the ff faces contributes at least kk edges to this count). However, when you count the same incidences by considering each edge, you get exactly 2e2e incidences, because every edge bounds exactly 2 faces. Since you're counting the same thing two ways, the constraint "at least kk edges per face" gives you kf≤2ekf \leq 2e. Answer A (kf=2ekf = 2e) would only hold if every face has exactly kk edges, but the problem states "at least kk" edges. Answer B (kf≥2ekf \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 kk edges, not fewer. Answer D (2f≤ke2f \leq ke) rearranges terms incorrectly and doesn't follow from the given constraints. The correct answer is C: kf≤2ekf \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.

Question 3

In analyzing a connected planar graph, you find that it has 77 faces (including the outer face) and 1111 edges. If you add one new vertex by subdividing an existing edge, what will be the number of faces in the resulting graph?

  1. 77 (correct answer)
  2. 88
  3. 66
  4. 99
Explanation: When subdividing an edge, we add one vertex and one edge (the original edge becomes two edges). Original: v−11+7=2v - 11 + 7 = 2, so v=6v = 6. After subdivision: v′=7v' = 7, e′=12e' = 12. By Euler's formula: f′=2−v′+e′=2−7+12=7f' = 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.

Question 4

If you remove one edge from a connected planar graph with vv vertices, ee edges, and ff faces, the resulting graph remains connected. What is the relationship between the number of faces in the new graph?

  1. The new graph has f−2f - 2 faces
  2. The new graph has ff faces
  3. The new graph has f+1f + 1 faces
  4. The new graph has f−1f - 1 faces (correct answer)
Explanation: 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=2v - 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=2v - e + f = 2. After removing one edge, you have vv vertices, e−1e-1 edges, and the new number of faces must satisfy: v−(e−1)+fnew=2v - (e-1) + f_{new} = 2. Solving for fnewf_{new}: fnew=2−v+e−1=(2−v+e)−1=f−1f_{new} = 2 - v + e - 1 = (2 - v + e) - 1 = f - 1. Choice A (f−2f-2) would require removing two faces, which doesn't happen from a single edge removal. Choice B (ff) 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+1f+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.

Question 5

A simple connected planar graph has 1212 vertices, and each vertex has degree 33. If this graph is drawn in the plane without edge crossings, how many faces does it have?

  1. 66
  2. 88 (correct answer)
  3. 77
  4. 55
Explanation: First find the number of edges: since each vertex has degree 3, the sum of degrees is 12×3=3612 \times 3 = 36. By the handshaking lemma, 2e=362e = 36, so e=18e = 18. Using Euler's formula: v−e+f=2v - e + f = 2 gives 12−18+f=212 - 18 + f = 2, so f=8f = 8. Choice A forgets the outer face. Choice C uses e=15e = 15 incorrectly. Choice D uses e=21e = 21 incorrectly.

Question 6

A wheel graph WnW_n consists of a cycle CnC_n plus one central vertex connected to all vertices of the cycle. For W7W_7 (wheel with 77-cycle), how many faces does the planar embedding have?

  1. 77
  2. 99
  3. 88 (correct answer)
  4. 1010
Explanation: When working with planar graphs, you'll often need to count faces using Euler's formula: V−E+F=2V - E + F = 2, where VV is vertices, EE is edges, and FF is faces (including the outer face). For wheel graph W7W_7, let's identify the components. You have a 7-cycle C7C_7 with 7 vertices, plus one central vertex connected to all cycle vertices. This gives you V=7+1=8V = 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=14E = 7 + 7 = 14 edges. Using Euler's formula: 8−14+F=28 - 14 + F = 2, which gives F=8F = 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 WnW_n, remember the pattern: you get nn triangular faces plus 1 outer face, totaling n+1n + 1 faces. This direct counting often provides a good check against Euler's formula calculations.

Question 7

A simple connected planar graph has the property that every vertex has degree at least 33. If the graph has nn vertices, what is the minimum number of faces it must have?

  1. n2+2\frac{n}{2} + 2 (correct answer)
  2. n+42\frac{n + 4}{2}
  3. n−1n - 1
  4. 3n−42\frac{3n - 4}{2}
Explanation: Since each vertex has degree at least 3, we have 2e≥3n2e \geq 3n, so e≥3n2e \geq \frac{3n}{2}. From Euler's formula: f=2−n+e≥2−n+3n2=2+n2=n2+2f = 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≥3n2−2f \geq \frac{3n}{2} - 2 incorrectly.

Question 8

A connected planar graph GG has 1515 vertices and 2222 edges. When drawn in the plane without edge crossings, what is the number of faces (including the outer face)?

  1. 88
  2. 99 (correct answer)
  3. 77
  4. 1010
Explanation: By Euler's formula for connected planar graphs: v−e+f=2v - e + f = 2. Substituting v=15v = 15 and e=22e = 22: 15−22+f=215 - 22 + f = 2, so f=9f = 9. Choice A results from the error 15−22+f=115 - 22 + f = 1. Choice C results from forgetting to count the outer face. Choice D results from the error v+e−f=2v + e - f = 2.

Question 9

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?

  1. 16
  2. 18
  3. 20 (correct answer)
  4. 24
Explanation: If every face is bounded by 4 edges, then counting face-edge incidences gives 4F=2E4F = 2E (each edge borders exactly 2 faces). With F=10F = 10, we get 4(10)=2E4(10) = 2E, so E=20E = 20. We can verify this is consistent with Euler's formula: V−E+F=2V - E + F = 2 gives V−20+10=2V - 20 + 10 = 2, so V=12V = 12.

Question 10

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?

  1. 8 (correct answer)
  2. 9
  3. 10
  4. 11
Explanation: Using Euler's formula for connected planar graphs: V−E+F=2V - E + F = 2. With V=12V = 12 and E=18E = 18, we get 12−18+F=212 - 18 + F = 2, so F=8F = 8. This is both the minimum and exact number of faces for any planar embedding of this graph.

Question 11

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?

  1. 8
  2. 9
  3. 10 (correct answer)
  4. 11
Explanation: The sum of the degrees of all faces equals 2E2E (since each edge is counted twice when summing face degrees). Given that this sum is 20, we have 2E=202E = 20, so E=10E = 10. We can verify using Euler's formula: V−E+F=2V - E + F = 2 gives 7−10+F=27 - 10 + F = 2, so F=5F = 5.