MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
I guess you want to add a link; say this one: – Anton Petrunin Jan 18 '10 at 4:53
up vote 3 down vote accepted

Yes it is true, it follows easily from Tutte's disjoint tree theorem for k=2:

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|cite|improve this answer
Thanks! This is much more general than I expected it to be. – zeb Jan 18 '10 at 21:11

Your Answer


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.