Is the 3-connected graph(s) on $n$ vertices with the minimum number of spanning trees always planar?
$\begingroup$
$\endgroup$
12
-
$\begingroup$ I like this question, but I am wondering if you have any particular motivation for this. $\endgroup$– Matthew KahleCommented Oct 14, 2010 at 18:44
-
$\begingroup$ This question came up when considering an old conjecture of Tutte "Among all 3-connected planar graphs with 2m edges, the graph with the smallest number of spanning trees is the wheel W(m+1)" which is wrong. Then it became interesting to look at a more general version of this question. $\endgroup$– utdiscantCommented Oct 14, 2010 at 19:17
-
2$\begingroup$ As stated in my previous comment, that is what Tutte conjectured, but this is wrong, and a counter example can be found at 30 edges. Take a path of length 2 and a path of length 12, then glue each vertex from the short path to each vertex of the long path. This graph is 3-connected, planar and has fewer vertices than the wheel-graph of the same size. $\endgroup$– utdiscantCommented Oct 14, 2010 at 19:27
-
1$\begingroup$ It is not true that all minimal 3-connected graphs are planar, look for example at K3,3. $\endgroup$– utdiscantCommented Oct 15, 2010 at 2:07
-
1$\begingroup$ The "other post" that Gwyn mentioned seems to be mathoverflow.net/questions/42189/…, and the paper is Fisher, Fraughnaugh, Langley, "P_3 connected graphs of minimal size". Unfortunately, P_3 connectivity seems to be rather different from standard 3-connectivity. $\endgroup$– Dylan ThurstonCommented Oct 16, 2010 at 21:11
|
Show 7 more comments
1 Answer
$\begingroup$
$\endgroup$
3
Edit. As it turned out I was not using the right switch for plantri.
This is therefore not an answer anymore but rather an extended comment for the case $n=11.$
As it turns out the minimal number of spanning trees of a 3-connected planar graph of order 11 is 3965 and is attained by the graph on the figure bellow.
alt text http://shrani.si/f/3f/IS/jiP8yvQ/pmin.png
As for the non-planar 3-connected graph I am yet to compute the answer. I'll post the result here as soon as it gets computed.
-
1$\begingroup$ What about the following graph imgur.com/Eow3L6L which have 3965 spanning trees? $\endgroup$ Commented Feb 7, 2013 at 11:26
-
$\begingroup$ Weird. I'll try to run the program again and see why the proposed graph is not found. It clearly looks like a counterexample to the stated answer! $\endgroup$– JernejCommented Feb 7, 2013 at 12:46
-