| The number of spanning trees in a planar graph (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Theorem 1. (1) A planar graph with n vertices has at most 5.33333333... n spanning trees. (2) A planar graph with n vertices and without a triangle has at most ( 4 8 √ e)n < 3.529988 n spanning trees. (3) A three-connected planar graph with n vertices and without a face cycle of length three or four has at most ( 3 √ 36/e 4/27) n < 2.847263 n spanning trees. Lower bounds that complement parts (1) and (2) come from the triangular and square grids [7], which have asymptotically ≈ 5.029545n and ≈ 3.209912n spanning trees, respectively, see also [6, (2.17–2.19)]. (The exact values are exp � 3 √ 3 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||