2
$\begingroup$

I was playing around with the Shannon Switching Game for some planar graphs, trying to get some intuition for the strategy, when I noticed a pattern. Since I only played on planar graphs, I'll restrict the problem to those for now, but we can also ask the problem for non-planar graphs.

Call a graph feasible if $E \ge 2V-2$, where $E$ is the number of edges and $V$ the number of vertices on the graph. Call a graph a minimal feasible graph if none of its proper subgraphs containing at least two vertices are feasible.

Is every minimal feasible graph a winning position for Short, regardless of which pair of vertices he has to connect? In other words, for those who don't know the solution to the Shannon Switching Game, is it true that every minimal feasible graph contains two edge-disjoint spanning trees?

If this is true, I think it provides a more "intuitive" way of looking at the Shannon Switching Game in actual play, where you can't spend your time drawing cospanning trees on your notebook - look for the smallest subgraph with more edges than it deserves, mentally collapse it to a point, and repeat.

$\endgroup$
3
$\begingroup$

Yes it is true, it follows easily from Tutte's disjoint tree theorem for k=2: http://lemon.cs.elte.hu/egres/open/Tutte%27s_disjoint_tree_theorem

In every partition class with n_i vertices you can have at most 2n_i-3 edges, plus the edges between the partitions, but this together still gives only 2n-2-|P| edges, where |P| is the number of partitions.

(This is joint answer with Filip Moric who does not have a MO account.)

$\endgroup$
  • $\begingroup$ Thanks! This is much more general than I expected it to be. $\endgroup$ – zeb Jan 18 '10 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.