Tutte’s conjecture on minimum number of spanning trees of 3-connected graphs

Seongmin Ok (옥성민)

Department of Applied Mathematics and Computer Science , Technical University of Denmark, Denmark

Department of Applied Mathematics and Computer Science , Technical University of Denmark, Denmark

2015/11/4 Wed 5PM-6PM

In Bondy and Murty’s book the authors wrote that Tutte conjectured the wheels have the fewest spanning trees out of all 3-connected graphs on fixed number of vertices. The statement can easily be shown to be false and the corrected version, where we fix the number of edges and consider only the planar graphs, were also found to be false. We prove that if we consider the cycles instead of spanning trees then the wheels are indeed extremal. We also establish a lower bound for the number of spanning trees and suggest the prisms as possible extremal graphs.

Tags: 옥성민