Maximum genus, connectivity, and Nebeský's Theorem
Maximum genus, connectivity, and Nebeský's Theorem
We prove lower bounds on the maximum genus of a graph in terms of its connectivity and Betti number (cycle rank). These bounds are tight for all possible values of edge-connectivity and vertex-connectivity and for both simple and non-simple graphs. The use of Nebeský's characterization of maximum genus gives us …