Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
I guess you want to add a link; say this one: en.wikipedia.org/wiki/Shannon_switching_game –  Anton Petrunin Jan 18 '10 at 4:53
add comment

1 Answer 1

up vote 3 down vote accepted

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.)

share|improve this answer
    
Thanks! This is much more general than I expected it to be. –  zeb Jan 18 '10 at 21:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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