4
$\begingroup$

How many planar graphs that satisfies $\forall\ v\in V\deg(v)\ge4$ are there?

If there are finite numbers, can you list them/link them?

If there are infinite, is there a proof?

I assume there are infinite, as if there are only a finite number, the Four Color Theorem (which led to this question) would be trivial.

$\endgroup$
3
  • $\begingroup$ It's really not good to change a question once you've received an answer. Better to ask a new question (and link each to the other). $\endgroup$
    – Gerry Myerson
    Commented Jul 30, 2022 at 12:41
  • 1
    $\begingroup$ For another infinite family, note that the edges of an octahedron form a planar graph with all vertices of degree four, and just join as many octahedra as you like together to get more examples. $\endgroup$
    – Gerry Myerson
    Commented Jul 30, 2022 at 12:43
  • $\begingroup$ OK, I will do that, G.M. $\endgroup$
    – Number Basher
    Commented Jul 30, 2022 at 12:51

1 Answer 1

Reset to default
9
$\begingroup$

Yes, there are infinitely many of them.

Here's an example: a graph made of vertices arranged in a $5 \times 5$ square grid, and for each side of the grid, there is an extra vertex that is adjacent to all 'outer' vertices of that side.

An example of a planar graph with minimum degree 4

It's quite obvious that the planar graph above satisfies the minimum degree $4$ requirement. In fact, as long as the grid is $4 \times 4$ or larger, the requirement will be satisfied. Hence, there's an infinite number of such graphs.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .