The Game of Graph Nim on graphs with four edges

Sayar Karmakar, Moumanti Podder, Souvik Roy, Soumyarup Sadhukhan · 2025

Read The Game of Graph Nim on graphs with four edges by Sayar Karmakar, Moumanti Podder, Souvik Roy, Soumyarup Sadhukhan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-05064.txt.

Introduction

Graph Nim turns a small graph into a two-player contest over edge weights. Sayar Karmakar, lead author with three co-authors, analyse that game on all graphs with exactly four edges in a 2025 combinatorics paper. On each turn, a player picks a vertex and reduces the weights of its edges, removing a positive total amount.

The player who makes the last move wins, so each starting weight pattern is either winning or losing for the first player. The authors characterise those patterns almost completely across the four-edge graphs. One graph resists full characterisation, and for it they provide substantial partial results.

Catalog record

CREATORSayar Karmakar, Moumanti Podder, Souvik Roy, Soumyarup Sadhukhan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE239 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-05064

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Game of Graph Nim on graphs with four edges Sayar Karmakar, Moumanti Podder, Souvik Roy, Soumyarup Sadhukhan Abstract . This work is concerned with the study of the Game of Graph Nim – a class of two-player combinatorial games – on graphs with 4 4 edges. To each edge of such a graph is assigned a positive-integer-valued edge-weight, and during each round of the game, the player whose turn it is to make a move selects a vertex, and removes a non-negative integer edge-weight from each of the edges incident on that vertex, such that (i) the remaining edge-weight on each of these edges is a non-negative integer, (ii) and the total edge-weight removed during a round is strictly positive. The game continues for as long as the sum of the edge-weights remaining on all edges of the graph is strictly positive, and the player who plays the last round wins. An initial configuration of edge-weights is considered winning if the player who plays the first round wins the game, whereas it is defined as losing if the player who plays the second round wins. In this paper, we characterize, almost entirely , all winning and losing configurations for this game on all graphs with precisely 4 4 edges each. Only one such graph defies our attempt to fully characterize the winning and losing configurations of edge-weights on its edges – we are still able to provide a significant set of partial results pertaining to this graph. 2020 Mathematics Subject Classification 05C57, 91A43, 91A46, 91A05, 05C22 1. Introduction and a formal description of the Game of Graph Nim The Game of Nim is one of the earliest examples of two-player combinatorial games , purported to have originated in ancient China and mentioned in European references that date back to as early as the 16th century. While several variants of this game are in existence, we describe here one of the most commonly studied versions, as follows: Definition 1.1 (The Game of Nim) . The game begins with k piles or heaps of chips, with the i -th pile containing x_{i} chips for i\in\{1,2,\ldots,k\} , where x_{1},x_{2},\ldots,x_{k} are positive integers. Two players take turns to make moves, where a move involves choosing a pile (that is not already empty) and subsequently removing at least one chip from that pile. The game continues until all the piles have been rendered empty, and the player to remove the very last chip is declared the winner. The set \{x_{1},x_{2},\ldots,x_{k}\} is referred to as the initial configuration or initial position of the game, and it is referred to as a winning position if the player who plays the first round is destined to win the game, whereas it is referred to as a losing position if the player who plays the first round is destined to lose the game. This is a perfect information game , as the piles of chips are revealed in their entirety to the two players before the game begins. This game has been studied extensively, and its winning and losing positions have been characterized fully (see, for instance, the seminal work done in [ 2 ] , as well as [ 6 ] and [ 9 ] for a more detailed literature on these games). In this paper, in some of our proofs, we have made use of the necessary and sufficient condition for an initial configuration to be winning for the Game of Nim defined in 1.1 (we refer the reader to Theorem 2.1 for a description of the same). The game we study in this paper is inspired by the Game of Nim, and played on a graph. As far as we are aware, this game, henceforth referred to as the Game of Graph Nim , was introduced and studied in [ 23 ] , and our work in this paper serves as both a significant extension to the results obtained in [ 23 ] and to show that the analysis required herein is far more complicated and ad hoc (in the sense that it depends heavily on the underlying graph on which the game is being played) compared to the Game of Nim in 1.1 . In what follows, we denote by G=(V,E) an undirected graph whose set of vertices is given by V and whose set of edges is given by E . For u,v\in V , we let \{u,v\} denote the edge between these two vertices if they are adjacent (i.e. if \{u,v\}\in E ). Henceforth, we let \mathbb{N} denote the set of all positive integers and \mathbb{N}_{0} the set of all non-negative integers. Definition 1.2 (The Game of Graph Nim) . Consider a graph G=(V,E) , with an edge-weight w_{0}(e) , where w_{0}(e)\in\mathbb{N}_{0} , assigned to each e\in E . Two players take turns (each such turn is, henceforth, referred to as a round ) to make moves, where a move involves (i) selecting a vertex u\in V , (ii) removing a non-negative integer weight from each edge \{u,v\}\in E (i.e. each edge in E that is incident on the vertex u ), so that the total weight removed is a strictly positive integer, and the remaining edge-weight of each \{u,v\}\in E is a non-negative integer. The game continues for as long as the edge-weight of each edge in E has not been reduced to 0 . The player to play the last round is declared the winner. Note that this game can be thought of as being played on the complete graph K_{|V|} with |V| many vertices, since for each pair of vertices u,v\in V with no edge present between u and v (i.e. \{u,v\}\notin E ), it is as if the initial edge-weight w_{0}(\{u,v\}) equals 0 . Henceforth, we let the players be referred to as P_{1} and P_{2} , with P_{1} assumed to play the first round. Given the underlying graph G=(V,E) , we call \left(w_{0}(e):e\in E\right) a winning initial weight configuration (or, simply, a winning configuration ) if the player who plays the first round of the game on G , starting with these initial edge-weights, is destined to win. We call \left(w_{0}(e):e\in E\right) a losing initial weight configuration (or, simply, a losing configuration ) if the player who plays the first round is destined to lose the game. In this paper, our objective is to consider all graphs comprising precisely 4 edges, i.e. |E|=4 , and characterize the winning and losing configurations on each of them. It suffices to consider all unlabeled distinct graphs comprising 4 edges each, and barring one, we are able to provide a complete characterization of the winning and losing configurations on each of them. For the graph for which we are not able to obtain a full understanding of the winning and losing configurations, we provide partial results that are significant and that, we believe, are adequate in demonstrating to the reader the challenges faced when analysing the Game of Graph Nim on certain underlying graphs. 1.1. Organization of the rest of the paper Our paper is organized as follows. In § 2 , we explain how the Game of Graph Nim can be seen as a generalization (that can be played on

Read the complete text