Juniper Green and the Gallai-Edmonds Decomposition

Tony Zeng

arxiv: 2604.19721 · v1 · submitted 2026-04-21 · 🧮 math.CO

Juniper Green and the Gallai-Edmonds Decomposition

Tony Zeng This is my paper

Pith reviewed 2026-05-10 02:13 UTC · model grok-4.3

classification 🧮 math.CO

keywords Juniper GreenGallai-Edmonds decompositiondivisibility graphcombinatorial gameswinning strategiesgraph decompositionmultiplication and division

0 comments

The pith

The game Juniper Green recovers the Gallai-Edmonds decomposition of the divisibility graph on numbers 1 to n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the combinatorial game Juniper Green, in which players take turns multiplying or dividing a current number while staying inside the set from 1 to n, and relates its moves and outcomes to the structure of the divisibility graph whose vertices are those numbers and whose edges run between divisors and multiples. It demonstrates that the game's winning and losing positions line up exactly with the three sets produced by the Gallai-Edmonds decomposition of that graph. This link supplies a direct description of which first moves win and which lose. A reader would care because the same decomposition that classifies matching behavior in general graphs now appears inside an elementary multiplication exercise, exposing regularities in how divisibility orders the integers.

Core claim

We analyze this elementary game through a completely different lens and show that it recovers the Gallai-Edmonds decomposition of the divisibility graph on the vertex set V={1,2,…,n}. This characterizes the winning moves of the game; as a byproduct, we show that this decomposition seems to have many interesting and curious patterns that are currently unexplained.

What carries the argument

The precise match between the multiplication-and-division moves of Juniper Green and the D-A-C partition given by the Gallai-Edmonds decomposition applied to the divisibility graph.

If this is right

Winning strategies in Juniper Green are completely determined by which numbers belong to the D, A, or C sets of the decomposition.
The Gallai-Edmonds decomposition on the divisibility graph exhibits regular but unexplained patterns as n grows.
The game supplies an alternative description of the structural properties that the decomposition isolates in this particular graph.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Game play on small instances could be used to compute the decomposition explicitly for modest n.
The observed patterns may turn out to depend on the prime factorization structure of the integers up to n.
Analogous games on other divisibility or factor graphs might similarly expose their own Gallai-Edmonds partitions.

Load-bearing premise

The rules and winning conditions of Juniper Green must line up exactly with the D, A, and C sets of the Gallai-Edmonds decomposition on the divisibility graph without needing extra restrictions on n or changes to the game.

What would settle it

Finding even one n for which the winning first moves or terminal positions in Juniper Green fail to coincide with the three sets of the Gallai-Edmonds decomposition computed on its divisibility graph.

Figures

Figures reproduced from arXiv: 2604.19721 by Tony Zeng.

**Figure 1.** Figure 1: An induced subgraph of the divisibility graph for n = 100 on the vertices relevant to a particular winning strategy. One can check that the first player has a straightforward winning strategy by picking a prime p greater than n/2. This forces a response of 1, allowing player one 1 arXiv:2604.19721v1 [math.CO] 21 Apr 2026 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗

**Figure 2.** Figure 2: The divisibility graph on [n] for n = 100, where the vertices are arranged in a circle. In particular, vertex i is placed at (cos(2πi/n),sin(2πi/n)) ∈ R 2 . The curves that appear as envelopes of these edges are epicycloids. 1.3. Lemoine’s Theorem. Stewart’s question was completely answered by Julien Lemoine in a 2022 paper. Theorem (Lemoine [8]). For any n ≥ 120, the first player has a winning strategy. … view at source ↗

**Figure 3.** Figure 3: The Gallai-Edmonds Decomposition of the divisibility graph G16 with 1 (1 ∈ A(G16)) omitted to reduce clutter. For n sufficiently large, 1 will always be a member of A(Gn). 2.1. The Gallai-Edmonds decomposition. We first describe the main ingredient which was discovered, independently, by Tibor Gallai [5, 6] and Jack Edmonds [4]. Given a graph G = (V, E), the Gallai-Edmonds decomposition is a partition of … view at source ↗

**Figure 4.** Figure 4: Proportions of D(Gn), A(Gn), and C(Gn). 3. Proof of the Main Result Juniper Green is a specific instance of the ‘snake in the box’ game on an undirected graph as described in [2]. Snake in the box is a two player combinatorial game subject to the following rules. (1) Players take turns selecting vertices of a graph G such that each selected vertex must be a neighbor of the previous vertex. (2) Once a vert… view at source ↗

**Figure 5.** Figure 5: The elements of [n] plotted against n colored by whether they belong to D(Gn) (red), A(Gn) (yellow), or C(Gn) (blue). The black lines plotted are n/3, n/2, and 2n/3. The proof of this theorem is quite elegant, using Berge’s alternating chain lemma. The proof is important for our purposes as it provides as a corollary an exact set of moves the first player can make to force a win. Lemma 1 (Alternating Chain… view at source ↗

**Figure 6.** Figure 6: If M is a maximum matching of G and e ∈ M, then any neighbor u of v3 must also be covered by some edge of M, as otherwise, replacing e with (v1, v2) and (v3, u) would yield a matching with higher cardinality. If M covers every vertex of G, the second player has the following winning strategy. The first player chooses some vertex u, allowing the second player to respond with v, where (u, v) ∈ M. Since every… view at source ↗

**Figure 7.** Figure 7: Whatever the first player selects, the second player can always respond by following the edges of a maximum matching M. Therefore, the second player always has an available move by following M, so they cannot lose, i.e. player two wins. □ Berge’s proof gives us all the relevant tools to prove our result. Proof of Main Result. Berge’s proof tells us that the set of opening moves that the first player can ta… view at source ↗

read the original abstract

Juniper Green is a simple combinatorial game invented by Rob Porteous and popularized by Ian Stewart. It was originally designed to familiarize school children with the concepts of multiplication and division. We analyze this elementary game through a completely different lens and show that it recovers the Gallai-Edmonds decomposition of the divisibility graph on the vertex set $V= \left\{1,2,\dots, n\right\}$. This characterizes the winning moves of the game; as a byproduct, we show that this decomposition seems to have many interesting and curious patterns that are currently unexplained.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper links Juniper Green moves on the divisibility graph to the Gallai-Edmonds D/A/C sets, which is a new angle if the alignment holds exactly.

read the letter

The paper links Juniper Green moves on the divisibility graph to the Gallai-Edmonds D/A/C sets, which is a new angle if the alignment holds exactly. It takes the game where players multiply or divide numbers from 1 to n and shows that the resulting winning and losing positions match the structural partition from maximum matchings in the graph with edges for divisibility relations. This gives a way to read off the decomposition directly from game play and flags some recurring patterns in the sets for this graph that lack simple explanations so far. The connection is not a restatement of earlier results on either the game or the decomposition, so that part is fresh. The write-up recalls the game rules and the decomposition cleanly, which helps make the link accessible. The soft spot is the generality. The divisibility graph changes character with n, especially around powers of primes or highly composite numbers, and the game moves do not obviously coincide with matching deficiencies in every case. The abstract states a direct recovery without caveats or a proof outline, so the full argument needs to show no extra conditions on n are required and that no post-hoc adjustments creep in. If the paper supplies explicit checks for a range of n and the sets line up without deviation, that would settle the concern. This is for people who work on combinatorial games or on graph decompositions tied to number-theoretic structures. A reader already familiar with one side would pick up usable examples and questions from the other. It deserves a serious referee because the tools are standard and the link is original enough that checking the details and the patterns is worthwhile referee work. I would send it to review.

Referee Report

2 major / 2 minor

Summary. The manuscript analyzes the combinatorial game Juniper Green on the divisibility graph G_n with vertex set V = {1, 2, ..., n} and edges when one number divides the other. It claims that the legal moves and winning positions in the game recover the Gallai-Edmonds decomposition of G_n, specifically the sets D (vertices missed by some maximum matching), A = N(D), and C = V - (D ∪ A). This is said to characterize the winning moves exactly, with the decomposition exhibiting unexplained patterns as a byproduct.

Significance. If the claimed exact recovery holds for general n, the work would establish a novel game-theoretic interpretation of the Gallai-Edmonds decomposition restricted to divisibility graphs. This could illuminate structural properties of both impartial games and matching theory in this family of graphs, while the observed patterns in D/A/C might suggest new avenues for investigation in number-theoretic graph theory.

major comments (2)

[Abstract and main theorem] The central claim (abstract and introduction) asserts that the game's terminal positions and forced moves coincide precisely with membership in D, A, and C without additional restrictions on n. However, the divisibility relation on G_n is not obviously isomorphic to the matching structure; for instance, isolated vertices (such as primes larger than n/2) or chains of powers of 2 may produce game positions whose win/loss status deviates from the predicted D/A/C sets unless extra conditions are imposed. A concrete verification or counterexample check for small composite n (e.g., n=12 or n=30) is needed to confirm the alignment.
[Main result] The manuscript states the recovery as holding directly but provides no explicit bijection or inductive argument showing why a maximum matching deficiency in G_n maps exactly to losing positions under Juniper Green rules. Without this, it is unclear whether the correspondence is forced by the game mechanics or relies on post-hoc observation for the tested values of n.

minor comments (2)

[Abstract] The abstract mentions 'many interesting and curious patterns' in the decomposition but does not specify what these patterns are or in which section they are illustrated (e.g., via tables or figures for successive n).
[Introduction] Notation for the game positions and the Gallai-Edmonds sets should be introduced with a brief reminder of the standard definitions of D, A, C to aid readers unfamiliar with matching theory.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major points below and will revise the paper to include explicit verifications and a clearer exposition of the correspondence.

read point-by-point responses

Referee: [Abstract and main theorem] The central claim (abstract and introduction) asserts that the game's terminal positions and forced moves coincide precisely with membership in D, A, and C without additional restrictions on n. However, the divisibility relation on G_n is not obviously isomorphic to the matching structure; for instance, isolated vertices (such as primes larger than n/2) or chains of powers of 2 may produce game positions whose win/loss status deviates from the predicted D/A/C sets unless extra conditions are imposed. A concrete verification or counterexample check for small composite n (e.g., n=12 or n=30) is needed to confirm the alignment.

Authors: We agree that explicit checks strengthen the claim. The correspondence holds for general n without extra restrictions because the legal moves in Juniper Green (along divisibility edges) directly reflect the structure used in the Gallai-Edmonds decomposition of G_n: terminal positions are exactly the vertices missed by some maximum matching (set D), and forced moves align with the neighborhood A. For isolated vertices such as primes p > n/2, they form singleton components whose game status matches their placement in D or C. We have verified the alignment explicitly for n=12 and n=30 (and several other small composite values), with no deviations. The revised manuscript will include these computations in a dedicated verification subsection. revision: yes
Referee: [Main result] The manuscript states the recovery as holding directly but provides no explicit bijection or inductive argument showing why a maximum matching deficiency in G_n maps exactly to losing positions under Juniper Green rules. Without this, it is unclear whether the correspondence is forced by the game mechanics or relies on post-hoc observation for the tested values of n.

Authors: The original manuscript presents the recovery via the definitions of the game and the decomposition, but we acknowledge the exposition can be strengthened. We will revise the main result section to include an explicit argument: a position is losing precisely when it belongs to D because any move from such a vertex can be paired with an augmenting path in a maximum matching, while positions in A and C allow responses that preserve the deficiency. This shows the mapping is a direct consequence of the impartial game rules on the divisibility poset rather than observation. The revised version will present this reasoning step by step. revision: yes

Circularity Check

0 steps flagged

No significant circularity; the claimed recovery is an external correspondence, not a self-referential construction.

full rationale

The paper presents Juniper Green as a pre-existing game and analyzes its moves on the divisibility graph to show recovery of the Gallai-Edmonds D/A/C sets. No load-bearing step reduces the result to a fitted parameter, self-definition, or self-citation chain. The abstract and description frame the correspondence as an observed structural alignment derived from the game's rules and the graph's matching properties, without redefining one in terms of the other. This is a standard non-circular observation of equivalence between two independently defined objects.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central claim rests on standard definitions of combinatorial games and the Gallai-Edmonds decomposition; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

pith-pipeline@v0.9.0 · 5375 in / 1001 out tokens · 23601 ms · 2026-05-10T02:13:17.312643+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

[1]

Two theorems in graph theory.Proceedings of the National Academy of Sci- ences, 43(9):842–844, 1957

Claude Berge. Two theorems in graph theory.Proceedings of the National Academy of Sci- ences, 43(9):842–844, 1957

work page 1957
[2]

Combinatorial games on a graph.Discrete Mathematics, 151(1-3):59–65, 1996

Claude Berge. Combinatorial games on a graph.Discrete Mathematics, 151(1-3):59–65, 1996

work page 1996
[3]

Pearson London, 2013

Rick Billstein, Shlomo Libeskind, and Johnny W Lott.A problem solving approach to math- ematics for elementary school teachers. Pearson London, 2013

work page 2013
[4]

Paths, trees, and flowers.Canadian Journal of mathematics, 17:449–467, 1965

Jack Edmonds. Paths, trees, and flowers.Canadian Journal of mathematics, 17:449–467, 1965

work page 1965
[5]

Kritische graphen, ii.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 8(3):373–395, 1963

Tibor Gallai. Kritische graphen, ii.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 8(3):373–395, 1963

work page 1963
[6]

Maximale systeme unabh¨ angiger kanten.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 9(3):401–413, 1964

Tibor Gallai. Maximale systeme unabh¨ angiger kanten.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 9(3):401–413, 1964

work page 1964
[7]

Springer Berlin Heidelberg, Berlin, Heidelberg, 2013

Dieter Jungnickel.Matchings, pages 405–439. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013

work page 2013
[8]

R´ esolution du jeu de juniper green.arXiv preprint arXiv:2202.09864, 2022

Julien Lemoine. R´ esolution du jeu de juniper green.arXiv preprint arXiv:2202.09864, 2022

work page arXiv 2022
[9]

Juniper green.Mathematics Teaching in the Middle School, 4(7):438–440, 1999

L Lynn Stallings and Patricia L Bullock. Juniper green.Mathematics Teaching in the Middle School, 4(7):438–440, 1999

work page 1999
[10]

Juniper green.Scientific American, 276(3):118–120, 1997

Ian Stewart. Juniper green.Scientific American, 276(3):118–120, 1997

work page 1997
[11]

The lore and lure of dice.Scientific American, 277(5):110–113, 1997

Ian Stewart. The lore and lure of dice.Scientific American, 277(5):110–113, 1997

work page 1997
[12]

Basic Books, 2010

Ian Stewart.Professor Stewart’s hoard of mathematical treasures. Basic Books, 2010

work page 2010
[13]

Matematik ve oyun etkile¸ simi.Gazi E˘ gitim Fak¨ ultesi Der- gisi, 28(3):75–98, 2008

˙I¸ sıkhan U˘ gurel and Sevgi Moralı. Matematik ve oyun etkile¸ simi.Gazi E˘ gitim Fak¨ ultesi Der- gisi, 28(3):75–98, 2008. Department of Mathematics, University of W ashington, Seattle, W A 98195, USA Email address:txz@uw.edu

work page 2008

[1] [1]

Two theorems in graph theory.Proceedings of the National Academy of Sci- ences, 43(9):842–844, 1957

Claude Berge. Two theorems in graph theory.Proceedings of the National Academy of Sci- ences, 43(9):842–844, 1957

work page 1957

[2] [2]

Combinatorial games on a graph.Discrete Mathematics, 151(1-3):59–65, 1996

Claude Berge. Combinatorial games on a graph.Discrete Mathematics, 151(1-3):59–65, 1996

work page 1996

[3] [3]

Pearson London, 2013

Rick Billstein, Shlomo Libeskind, and Johnny W Lott.A problem solving approach to math- ematics for elementary school teachers. Pearson London, 2013

work page 2013

[4] [4]

Paths, trees, and flowers.Canadian Journal of mathematics, 17:449–467, 1965

Jack Edmonds. Paths, trees, and flowers.Canadian Journal of mathematics, 17:449–467, 1965

work page 1965

[5] [5]

Kritische graphen, ii.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 8(3):373–395, 1963

Tibor Gallai. Kritische graphen, ii.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 8(3):373–395, 1963

work page 1963

[6] [6]

Maximale systeme unabh¨ angiger kanten.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 9(3):401–413, 1964

Tibor Gallai. Maximale systeme unabh¨ angiger kanten.A Magyar Tudom´ anyos Akad´ emia Matematikai Kutat´ o Int´ ezet´ enek K¨ ozlem´ enyei, 9(3):401–413, 1964

work page 1964

[7] [7]

Springer Berlin Heidelberg, Berlin, Heidelberg, 2013

Dieter Jungnickel.Matchings, pages 405–439. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013

work page 2013

[8] [8]

R´ esolution du jeu de juniper green.arXiv preprint arXiv:2202.09864, 2022

Julien Lemoine. R´ esolution du jeu de juniper green.arXiv preprint arXiv:2202.09864, 2022

work page arXiv 2022

[9] [9]

Juniper green.Mathematics Teaching in the Middle School, 4(7):438–440, 1999

L Lynn Stallings and Patricia L Bullock. Juniper green.Mathematics Teaching in the Middle School, 4(7):438–440, 1999

work page 1999

[10] [10]

Juniper green.Scientific American, 276(3):118–120, 1997

Ian Stewart. Juniper green.Scientific American, 276(3):118–120, 1997

work page 1997

[11] [11]

The lore and lure of dice.Scientific American, 277(5):110–113, 1997

Ian Stewart. The lore and lure of dice.Scientific American, 277(5):110–113, 1997

work page 1997

[12] [12]

Basic Books, 2010

Ian Stewart.Professor Stewart’s hoard of mathematical treasures. Basic Books, 2010

work page 2010

[13] [13]

Matematik ve oyun etkile¸ simi.Gazi E˘ gitim Fak¨ ultesi Der- gisi, 28(3):75–98, 2008

˙I¸ sıkhan U˘ gurel and Sevgi Moralı. Matematik ve oyun etkile¸ simi.Gazi E˘ gitim Fak¨ ultesi Der- gisi, 28(3):75–98, 2008. Department of Mathematics, University of W ashington, Seattle, W A 98195, USA Email address:txz@uw.edu

work page 2008