This is an excellent question that delves into the nuances of applying combinatorial game theory to games with non-standard winning conditions. You've already made the most crucial observations, which are the key to unlocking the game's structure. Let's formalize and extend your findings.

Summary of Key Insights

You correctly identified:

1. The Core Problem: The standard decomposition of a game on a graph into a nim-sum fails because the win condition is global. The game isn't over until the entire graph is edgeless.
2. The Parity Equivalence: Any graph is equivalent to a graph , where is the "core" of (the subgraph of non-isolated vertices), and is the parity of the number of isolated vertices. This is because adding or removing pairs of isolated vertices () is a "neutral" move that can be mirrored by the opponent, making .
3. The Parity Matters: For any non-null core graph , the games (i.e., ) and are not equivalent, as shown by your strategy-stealing argument.

These insights form the foundation for a complete analysis. The "extension of Sprague-Grundy theory" you're looking for involves characterizing a game not by a single nim-value, but by a pair of nim-values that depend on the parity of isolated vertices.

An Extension of Sprague-Grundy for "Disconnect"

Let's define the state of the game not just by the graph, but by the pair , where is the core graph (no isolated vertices) and is the parity of isolated vertices. The original game on a graph corresponds to the state .

For any core graph , we need to compute two nim-values:

• : The nim-value of the game starting with state , i.e., the graph .
• : The nim-value of the game starting with state , i.e., the graph .

The nim-value of any graph is then simply .

We can compute these values using a coupled system of recursive formulas based on the mex rule.

Base Case: The simplest core graph is the null graph, .

• . (The game is on an empty graph or , which is already over and thus a P-position).
• . (The game on a single vertex is also already over). So, the base case is .

Recursive Step: For any non-null core graph , we compute from the values of "smaller" core graphs.

1. Calculating : The game starts at state , which is the graph . A move consists of removing a vertex . Let's analyze the result of removing . The new graph is . This graph might have a new core, , and some newly created isolated vertices. Let be the number of newly created isolated vertices. The state of the game after removing is . The nim-value of this resulting position is, by definition, . Thus, the formula for is:

2. Calculating : The game starts at state , which is the graph . There are two types of moves:

• Type (a): Remove the single isolated vertex. The resulting graph is , which corresponds to the state . The nim-value of this option is .
• Type (b): Remove a vertex . The resulting graph is . Again, let . So the new graph is . This corresponds to the state . The nim-value of this option is .

Combining these options, the formula for is:

This pair of coupled recurrences defines the nim-values for any state of the game.

Example: Calculating Values for and

Let's compute the value-pair for some simple core graphs.

A. Core graph

• .

• Removing (or ) leaves a single vertex . The new core is , and new isolated vertex is created.

• We need the base case values: .

• .

• .

So, for , the value-pair is . This means (an N-position) and (also an N-position).

B. Core graph (path on 3 vertices)

• Let with edges and .

• Move options from :

  1. Remove (or ): The remaining graph is . The new core is , and new isolated vertices are created. The resulting state is .
  2. Remove : The remaining graph is two isolated vertices, . The new core is , and new isolated vertices are created. The resulting state is .

• We need the values for the resulting cores: and .

• .

• .

So, for , the value-pair is .

Answers to Your Specific Questions

1. Are there any other general decomposition or equivalence results? The primary equivalence is the one you found: . This is the most powerful decomposition available. It partitions the set of all graphs into equivalence classes, where each class is defined by a unique core graph and a parity bit . The framework above shows how to compute the nim-value for any member of this class.

2. Any extension of the Sprague-Grundy theory to this class of games? Yes. The system of coupled recurrences for the value-pair is precisely that extension. It acknowledges that the game state has an extra parameter (parity of isolated vertices) and defines a vector of nim-values, one for each possible value of the parameter. This is a general technique for handling impartial games where moves can alter global parameters.

3. Is there some more refined equivalence relation ... such that can be determined in terms of and ? The equivalence class of a graph is best thought of as the pair . The nim-value of the game on is , which is determined by the "value" of the core graph , which is the pair .

Now consider the composition . Let and . The union will have a core of and a combined parity of . The nim-value of the game on is therefore: This value cannot be determined from and alone. You need the full information about their core graphs. For instance, knowing is not enough; you need to know which specific pair produced that value of 1.

The operation you're interested in is graph union, not the disjunctive sum of games. The Sprague-Grundy theorem's addition rule () applies to the disjunctive sum. Your game's composition rule (union) requires the more complex, tailored analysis described above. The framework of pairs is the correct way to analyze compositions under graph union for this game.