background Ludii Portal
Home of the Ludii General Game System


Home Games Forum Downloads Concepts Contribute Tutorials Tournaments World Map Ludemes About





Category Experimental, Graph theory


The SpanRups is a graph theory game that uses concepts of spanning tree, and spanning caterpillar tree. A spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. The spanning caterpillar tree C is a spanning tree in which all the vertices are within distance 1 from a central path.


Starting of the game, the player can select the goal of the puzzle, which can be spanning tree or caterpillar tree. This game has two versions: addition and deletion version. At the addition version, the board graph is initially uncoloured. Players take turns to colour an uncoloured edge by a common colour. After colouring some edges, if the player makes a spanning tree (or caterpillar tree), he wins. At the other version, the game starts with all the same coloured edges. At each turn, a player chooses to remove the colour of a coloured edge. After removing some coloured edges, if the player makes his desired tree (spanning or caterpillar tree), he wins.


Tahmina Begum

Creation date


Ludeme Description



Browse all concepts for SpanRups here.



     Contact Us

lkjh Maastricht University Data Science and Knowledge Engineering (DKE), Paul-Henri Spaaklaan 1, 6229 EN Maastricht, Netherlands Funded by a €2m ERC Consolidator Grant (#771292) from the European Research Council