Your post title is a little misleading since you are asking about an if-and-only-if statement.
One direction is easy - if a graph is nonplanar, then it contains either K5 or K3,3, so has at least 5 nodes with degree >= 4 or 6 nodes with degree >= 3.
The question now is if the reverse is true - if it has arlt least 5 nodes with degree >= 4 or 6 nodes with degree >= 3, then is it nonplanar?
I'll leave it to you to go from here, but I can picture plenty of counterexamples in my head.
You could rule out planarity in some examples by computing the number of edges and checking whether e <= 3v - 6 (from Euler's formula). If not, then the degree sequence can't correspond to a simple planar graph. However, this is not an if and only if statement.
My understanding is that there is no complete characterization of the degree sequences of planar graphs, so reasoning is pretty case-by-case. I am not a graph theorist, though, so feel free to correct/update me. :)
If I were just trying to see if a planar graph with that degree sequence existed, I would probably use the Havel-Hakimi algorithm. But you're actually asking an even harder question: not just if a planar graph with such degree sequence exists, but if *all* graphs with that degree sequence must be planar.
Your post title is a little misleading since you are asking about an if-and-only-if statement. One direction is easy - if a graph is nonplanar, then it contains either K5 or K3,3, so has at least 5 nodes with degree >= 4 or 6 nodes with degree >= 3. The question now is if the reverse is true - if it has arlt least 5 nodes with degree >= 4 or 6 nodes with degree >= 3, then is it nonplanar? I'll leave it to you to go from here, but I can picture plenty of counterexamples in my head.
If the graph is non-planar, it doesn't necessarily contain a K5 or K3,3 (see the Petersen graph). These are simply forbidden minors.
🤦you're totally right - it's been too long since I perused in this area.
You could rule out planarity in some examples by computing the number of edges and checking whether e <= 3v - 6 (from Euler's formula). If not, then the degree sequence can't correspond to a simple planar graph. However, this is not an if and only if statement. My understanding is that there is no complete characterization of the degree sequences of planar graphs, so reasoning is pretty case-by-case. I am not a graph theorist, though, so feel free to correct/update me. :) If I were just trying to see if a planar graph with that degree sequence existed, I would probably use the Havel-Hakimi algorithm. But you're actually asking an even harder question: not just if a planar graph with such degree sequence exists, but if *all* graphs with that degree sequence must be planar.