The number of spanning trees in a planar graph
In: Oberwolfach Reports, 2, European Mathematical Society -
Publishing House, 2005, pp. 969–973. doi:10.4171/OWR/2005/17
A planar graph with n
vertices has at most 5.333...n
spanning trees. If it
has no triangle, it has at most 3.53n spanning trees.
If it is
planar and without a face cycle of length three or four it has at most
trees. These bound are obtained with a probabilistic method.
They are applied to the construction of 3-dimensional polytopes with a
combinatorial structure and with small integral vertex
Last update: April 29, 2015.