• Which degree sequences are planar-graphical, that means for which degree sequences $$d_1,...,d_n$$ $$d_1\le...\le d_n$$ exists a PLANAR graph that has this degree sequence ?

    I found some links in the internet, but I did not find a concrete classification. I know Euler's polyeder formula and that at least one vertex must have degree less than $6$ and some similar restrictions, but I would like to have some more powerful conditions.


There is no complete classification of the degree sequences of planar graphs as of today. However, I do have an example for you of an infinite number of similar degree sequences that always contain a planar graph:

$ (N,N,N,N,4,4,4,4,...) $, where $ N > 4 $ and the number of $ 4's $ in the sequence is equal to $ (N-2)^2 $.

  • $\begingroup$ This seems like a very trivial result in this direction. Maybe a bit more interesting is that an $r$-regular planar graph on $n$ vertices always exists provided (1) $rn$ is even, the necessary condition for regular graphs (2) $\frac{rn}{2} \le 3n-6$, Euler's condition for planar graphs, and (3) $(r,n)$ is not $(4,7)$ or $(5,14)$. (source, I think) $\endgroup$ – Misha Lavrov Jul 18 '18 at 21:58
  • $\begingroup$ @MishaLavrov What makes it so trivial? $\endgroup$ – Ultradark Jul 18 '18 at 22:01
  • $\begingroup$ The fact that it's only about one very specific family of degree sequences. $\endgroup$ – Misha Lavrov Jul 18 '18 at 22:31
  • $\begingroup$ Just because it is specific does not mean it's trivial. $\endgroup$ – Ultradark Aug 8 '18 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.