Let G be a 3-regular plane graph with 12 faces. How many vertices does G have?

kybudmanqm

kybudmanqm

Answered question

2022-09-07

Let G be a 3-regular plane graph with 12 faces. How many vertices does G have?
This would be pretty easy to solve if I knew that G is connected by using Eulers formula | V | | E | + | F | = 2.
But I don't know how to show that G is connected. Am I on the wrong path? Or is there some combinatorial argument to count the vertices?

Answer & Explanation

Peugeota2p

Peugeota2p

Beginner2022-09-08Added 14 answers

Step 1
Without the assumption that G is connected, there are simply multiple solutions. You've probably already solved the connected case. But we can also:
- Take a graph with two connected components: a cube graph (with 5 bounded faces) and a pentagonal prism (with 6 bounded faces). The result has 11 bounded faces: 12 total. There are 18 vertices.
- Take a graph with three connected components: two tetrahedra and a triangular prism. The result has 3 + 3 + 4 bounded faces, and again 12 faces total. There are 16 vertices.
Step 2
In general, we can generalize Euler's formula to
| V | | E | + | F | = | C | + 1
where |C| is the number of connected components. The logic is this: we can add | C | 1 edges to the graph to connect the components, getting a connected graph with | E | + | C | 1 edges, but the same number of vertices and faces. Applying Euler's formula to the new graph gives us the generalized formula above.
In the general formula, you will not be able to solve for |V|, but you will get a relationship between |V| and |C|. We also have the inequality 1 | C | 1 4 | V | : there is always at least one component, and at most 1 4 | V | because the smallest 3-regular planar graph has 4 vertices. This gives us a range of possibilities for |V| and |C|.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?