This is from Graph Theory by Bondy. 1.6.2 For each positive integer d, describe a simple infinite planar graph with minimum degree d. I am confused about how to make sure every other vertices, rather than the vertex I chose to have the minimum degree, has degree greater or equal to the minimum degree? Is there any simple way to think about this kind of questions?


You can embed an infinite tree where each node has $d$ children in the plane.

The images of the edges as you go down the tree would have to get shorter very quickly. This might violate some criterion for an infinite graph being planar. Also, describing such a map from your graph into the plane in any kind of detail sounds a bit of a headache.

Here's about what it could look like for $d=3$. The root of the tree has degree four (in the center) and every other node has degree three. (if you are privy to algebraic topology, yes, this image is just the universal cover of the wedge of two circles)

Universal cover of wedge of two circles Image from: www.cs.le.ac.uk/people/rthomas/


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.