0
$\begingroup$

I am working on a problem about planar graphs and trying to understand if two statements can both be true at the same time. The problem states that for any planar graph with at least 3 or more vertices, the number of edges is limited by a known inequality.

The first statement is: (1) A planar graph must have a node with degree at most 5.

This makes sense to me because Euler's formula and the constraints on the number of edges in a planar graph mean that there must always be at least one vertex with degree 5 or less.

The second statement is: (2) At least half of the nodes in the graph must have a degree of at most 12.

Here is where I get confused. While it's true that no node in a planar graph can have a degree greater than 12, I am not sure if it is always guaranteed that at least half of the nodes have a degree of 12 or less.

So my question is: Is it possible for both (1) and (2) to be true at the same time? Or does (2) fail in some cases, making (1) the only valid statement? I would really appreciate any clarification or insights into whether (2) can ever hold true alongside (1).

I know that to maintain an average degree less than 6 while still satisfying the upper bound on vertex degrees (degree ≤ 12), the vast majority of the vertices must have a degree lower than 12. Specifically, at least half of the vertices must have degree 12 or less in order for the average degree to stay below 6.

Improve this question
New contributor
HSR is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
4
  • $\begingroup$ This will shortly be closed as it not research level; while waiting for this, you could think about the average degree of a vertex and see where that leads you. $\endgroup$
    – Gordon Royle
    Commented 9 hours ago
  • $\begingroup$ In that case (2) is consistent because to keep the average degree under 6 while obeying the maximum degree bound of 12, at least half of the vertices must have a degree at most 12, but in that case will it be conflict with (1)? $\endgroup$
    – HSR
    Commented 54 mins ago
  • $\begingroup$ I don't understand what makes you think that (1) and (2) are in any way in conflict. They both say that a planar graph must have enough vertices of low degree; they just quantify it in different ways. $\endgroup$
    – Emil Jeřábek
    Commented 31 mins ago
  • $\begingroup$ Because of the "at most" part for both statements. How can they coexist together if one is "at most 5" and another one is "at most 12"? $\endgroup$
    – HSR
    Commented 26 mins ago

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .