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.
No comments:
Post a Comment