Abstract: Let G be a connected graph and L(G) the set of all integers k such that G contains a spanning tree with exactly k leaves. In this talk we give a short proof of the fact that for a connected graph G, the set L(G) is contiguous. We then discuss a few consequences of this result, both structural and algorithmic. We also present bounds for f(n), which we define to be the largest integer k such that every plane 4-connected triangulation on n vertices contains a spanning tree with at least k leaves. This talk is based on joint work with Kenta Noguchi (Tokyo University of Science, Japan).
If you are interested in participating online (either regularly or only in a specific lecture), please contact Yulai Ma or Eckhard Steffen in advance so that the participation link can be shared.