Editing Shannon switching game (section)

== Rules ==
[[Image:Shannon_game_graph.svg|right|thumb|Player Cut took 3 turns (dotted edges), player Short took 4 turns (green edges).]]
The game is played on a finite [[Graph theory|graph]] with two special nodes, ''A'' and ''B''. Each edge of the graph can be either colored or removed. The two players are called ''Short'' and ''Cut'', and alternate moves. On Cut's turn, Cut deletes from the graph a non-colored edge of their choice. On Short's turn, Short colors any edge still in the graph.  If Cut manages to turn the graph into one where ''A'' and ''B'' are no longer connected, Cut wins. If Short manages to create a colored path from ''A'' to ''B'', Short wins. The game always terminates after a finite number of moves, and one of the two players has to win. Either Short, Cut, or the player moving first is guaranteed the existence of a winning strategy on any given graph.<ref>{{cite journal|author=Stephen M. Chase |year=1972|title=An implemented graph algorithm for winning Shannon Switching Games | journal=[[Communications of the ACM]] | volume=15 | pages=253–256|doi=10.1145/361284.361293|issue=4|s2cid=21110956|doi-access=free}}</ref>

The ''Short'' and ''Cut'' games are a duality; that is, the game can be restated so that both players have the same goal: to secure a certain edge set with distinguished edge ''e''. Short tries to secure the edge set that with ''e'' makes up a [[Cycle (graph theory)|circuit]], while Cut tries to secure an edge set that with ''e'' makes up a cutset, the minimal set of edges that connect two [[Glossary of graph theory#Subgraphs|subgraphs]].