On the maximum degree of path-pairable planar graphs (Q2415080): Difference between revisions

Summary: A graph is path-pairable if for any pairing of its vertices there exist edge-disjoint paths joining the vertices in each pair. We investigate the behaviour of the maximum degree in path-pairable planar graphs. We show that any \(n\)-vertex path-pairable planar graph must contain a vertex of degree linear in \(n\). Our result generalizes to graphs embeddable on a surface of finite genus.