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?


1 Answer 1


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, 2020 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, 2020 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, 2020 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, 2020 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, 2020 at 16:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .