The vertex-deletion game "Disconnect" can be analyzed using an extension of Sprague-Grundy theory by refining the equivalence relation to account for graph structure and isolated vertices. Here's the key insight:

A graph ( G ) can be decomposed into its non-isolated connected components (those with edges or size ≥2) and its isolated vertices. Let ( H ) be the union of non-isolated components,...

Yes. There is a clean way to “repair” Sprague–Grundy for this game and get exactly the kind of decomposition you want.

Key idea: strip off the isolated vertices (which are just “passes”) and play a standard impartial game on the rest.

Definitions.

• Let κ(G) be G with all isolated vertices deleted.
• Let p(G) be the parity (0/1) of the number of isolated vertices of G.
• Consider the restricted ...

Analyzing the "Disconnect" Vertex-Deletion Game

This question examines a graph-based combinatorial game called "Disconnect" where players take turns removing vertices, and the player who creates a completely disconnected graph (no edges) wins.

Understanding the Current Results

The question has already established several important properties:

1. For any graph G and even n, G ∪ K̄ₙ (G with...

Short answer. No.
Apart from the little trick with the isolated vertices that you have already discovered, the game “Disconnect’’ stubbornly refuses to split into smaller, independent parts. There is no non-trivial equivalence relation ≈ that

 (i) puts finitely (or even just few) graphs into the same class,
 (ii) guarantees that two equivalent graphs have the same nim–value, and
 (iii) ma...

<think> We are analyzing an impartial game called "Disconnect" played on graphs. Players alternately remove vertices, and the player who leaves a graph with no edges wins. The game is impartial, so Sprague-Grundy theory applies: each game position has a nim-value (or Grundy number) which is the mex (minimum excludant) of the nim-values of the positions reachable by one move.

However, the win cond...

Here is what one can say in complete generality.

1. “Disconnect” is an impartial misère‐type game. A position is a finite graph G with at least one edge, and a move is “delete one vertex.” Terminal positions are edgeless graphs (no edges)—as soon as you reach an edgeless graph the game stops and the last mover wins. In particular you cannot continue deleting isolated vertices once there...

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

Write 𝐺↦g(𝐺) for the Sprague–Grundy number (nim–value) of a graph in the game

Disconnect : “A move consists of deleting one vertex.
The player who makes the last edge disappear wins; at that moment the game stops and no further vertex may be removed.”

1. What happens when the position has no isolated vertices?
   If V⁺(𝐺) is the set of vertices whose degree is ≥1, every legal move must b...

This is a fascinating question about a vertex-deletion game where the winning condition is non-standard (producing a fully disconnected graph rather than having no moves left). Let me analyze the key aspects and explore potential extensions.

Key Observations from the Question

1. The game is impartial but has a non-standard winning condition
2. **Standard Sprague-Grundy decomposition fails...