Suppose that a connected planar graph has six vertices, each of degree four. Into how many regions is the plane divided by a planar representation of this graph?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. 8
Explanation
Edges = 6 × 4 / 2 = 12. Regions r = e − v + 2 = 12 − 6 + 2 = 8.
More Discrete Structures and Optimisation questions
- For which values of and does the complete k bipartite graph m,n have a Hamilton circuit?
- Which of the following is the principal conjunctive normal form of [(p ∨ q) ∧ ¬p] → ¬q?
- How many cards must be selected from a standard deck of 52 cards to guarantee that at least three hearts are present among them?
- Match List I with List II. List I: (a) p → q, (b) p ∨ q, (c) p ∧ q, (d) ¬(p → q). List II: (i) ¬(q → ¬p), (ii) p ∧ ¬q, (iii) ¬p → q, (iv) ¬…
- Find the zero-one matrix of the transitive closure of the relation with matrix A = [1 0 1; 0 1 0; 1 1 0].
- For the LPP: maximize Z = 2x₁ − x₂ + 2x₃ subject to 2x₁ + x₂ ≤ 10, x₁ + 2x₂ − 2x₃ ≤ 20, x₁ + 2x₃ ≤ 5, x₁, x₂, x₃ ≥ 0, what is the solution…