Does a (finite) planar graph $G$ with minimum degree 3 contain a vertex $v$ for which all vertices of distance r=2 neighbourhood consisting of bounded degree vertices?

If this is true, does it still work for larger r and on bounded genus graphs?

Somewhat motivated by Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 14?


I don't see any reason why this should be the case, or why your condition about degree 2 is here. You can take a tree embedded in the plane such that each vertex has countably infinite valence.

  • $\begingroup$ sorry I should have said no vertices of degree 2 or less $\endgroup$
    – Hao S
    Sep 13 '20 at 3:49
  • $\begingroup$ That still doesn't exclude the example I've given. I'm not really sure what you're looking for. $\endgroup$ Sep 13 '20 at 5:20
  • $\begingroup$ Are you talking about an infinite graph? If so let me clarify I'm talking about finite graphs. $\endgroup$
    – Hao S
    Sep 13 '20 at 16:41
  • $\begingroup$ Meaning finite vertex set? Well then your question is clearly true because the degrees of all vertices are bounded by just the maximum degree. $\endgroup$ Sep 13 '20 at 16:55
  • $\begingroup$ I mean is there some constant K such that for any finite planar graph of minimum degree 3 we can find a neighbourhood where all the vertices have degree less than K. $\endgroup$
    – Hao S
    Sep 13 '20 at 16:57

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.