K3-Saturator
By Roy Oursler
What is K3-Saturator
• K3-Saturator is a combinatorial game
• A combinatorial game is a two player game where both of
the players have perfect information, there are no chance
based moves, and the game’s outcome is either a win or a
loss.
• In combinatorial games, one of the players has a winning
strategy from the beginning of play, my goal was to find
who would be the winner in different games of K3-
Saturator.
• This game was partially explored by Michael Ferrara,
Michael Jacobson, and Angela Harris in their article The
Game of F-Saturator in Discrete Applied Mathematics
pages 189 through 197.
How to Play
• Setup: There are two players which start off
with some points drawn on a piece of
paper.
• Play: Each player takes turns connecting
two points together.
• Goal: The players do not want to connect
two points together that will form a
triangle.
Example Game
Note: In this game a triangle
is created when
1 4
connecting three
points together, lines
crossing do not create
a triangle. The three
connected points are a
type of graph called a
2 3 K3
Useful Definitions
• Graph- A graph is a set of points called vertices
that are connected by lines called edges.
• H-Saturated Graph- A H-saturated graph is
formed from two graphs, graph H and graph G.
Graph G is H saturated if G contains no copy of H
and the addition of any edge to G creates a copy
of H
• This is the reason for this game to be named K3
saturator.
Example Game
This is an example of a K3
1 4 saturated graph since no line
can be added that won’t form
one of the triangles.
2 3
Winning Strategy
• For the example game, the 2nd player can
always win it.
1 4 1 4
2 3 2 3
A Revision of the Game(version 2)
• Play the basic game with an even number of
points.
• Divide the points into pairs which are
poisoned pairs, or pairs which can’t be played
between.
Example Game
The winner of this modified game will always be the 2nd player
1 4 Red lines are
the moves
which aren’t
allowed.
2 3
The strategy for the 2nd player is to mirror the 1st players
moves between the poisoned pairs.
Example Game
1 6
2 5
3 4
Proof of the Winning Strategy
First, set the graph up so that it can be labeled in
the shown fashion.
The connections between any
1 two points i and j is written as n
{i , j}.
2 n-1 This means when the 1st player
connects the point {i , j} the
second player connects the
points {n-i+1,n-j+1} where n is
+1
the size of the graph.
…
…
Proof of Winning Strategy
Theorem:
If there is a graph G of even order n, which does not have
mirror symmetry, and one edge g can be added to G that
makes the graph have mirror symmetry, then either a K3
graph is not formed within G, or a K3 graph already existed
within G.
In this game, the second players strategy will always be creating
mirror symmetry while the 1st player is always destroying the
symmetry, so if a K3 forms, that K3 will have been created by the
first player.
Proof of Winning Strategy
• Assume the graph G is in a position such that a
K3 will be formed when the edge g is added to
G. Assume this K3 consists of the edges {a,b},
{b,c},and{a,c} where a, b, and c are points of
the graph. In this position, there are 3 cases to
deal with.
Proof of Winning Strategy
Case 1
Assume that the edge g is a reflection of itself. This edge does not affect mirror
symmetry which implies that G already had mirror symmetry. This is a
contradiction therefore g doesn’t exist.
Case2
Assume that none of the edges {a,b}, {b,c},and{a,c}are reflections of each other.
Due to the assumption that any two of the edges {a,b}, {b,c},and{a,c} aren’t
reflections of each other, then the K3 {n-a+1, n-b+1}, {n-b+1,n-c+1}, and {n-
a+1,n-c+1} must already have existed before g was added to the graph.
Proof of Winning Strategy
Case 3
Assume that of the edges in the K3 consisting of {a,b}, {b,c}, and {a,c}, and
{a,c} is a reflection of one of the other edges.
This implies that {a,c} = {n-a+1,n-b+1} or {n-b+1,n-a+1}.
Assume {a,c}= {n-a+1,n-b+1}
Then a = n-a+1
Then 2a+1 = n
This implies n is odd a contradiction.
Assume {a,c}= {n-b+1,n-a+1}.
Then a=n-b+1 and c=n-a+1
Then c+(n-b+1)=n-a+1+a
Then c-b+n+1=n+1
Then c=b, a contradiction.
Therefore a K3 didn’t form.
Proof of Winning Strategy
Therefore the theorem holds.
So the second player will always win in the
modified game
Using this theorem and a few others, I can prove
the winner on games of size 4,6,and 8.
Useful Definitions
In order to prove the winner on graphs of size 4,6
and 8 there are a few definitions which need to
be known.
A connected pair is formed when points in a pair
are connected by an edge.
An unconnected pair is formed when a pair is not
connected but still can be connected
A poisoned pair is formed when a pair cannot
become a connected pair without losing the
game.
Game(Version 3)
• Now for the game we will start the game off with
some number of poisoned, connected and
unconnected pairs.
• Also, play between the poisoned pairs and the
unconnected pairs is not allowed.
• For the original game, all the pairs would be
unconnected pairs.
• The strategy for this game is the same as in the
version 2 with the extra rule that the winning
player will keep the number of unconnected pairs
even.
Example Setup
1 6 This is a game of size
6 where we are
starting with a
poisoned pair, a
connected pair, and
an unconnected pair
2 5
3 4
Proof
• The follow theorems prove that the number of
poisoned pairs created during a game is an
even number.
• This allows for an unconnected pair to be a
the deciding move in this game.
Proof
Theorem :Play between connected pairs or
poisoned pairs with the rules of this game will not
create any additional poisoned pairs.
Proof
Because edges cannot be removed in this game,
connected pairs will always be connected pairs
and poisoned pairs will always be poisoned pairs.
Therefore the number of poisoned pairs cannot
be increased with those moves.
Proof
Theorem : Play between a connected pair and an
unconnected pair will never create a single poisoned
pair with the strategy being used.
Proof
Assume that there is a connected pair {a,b} and an
unconnected pair {c,d} and that a connection exists
that turns the pair {c,d} into a poisoned pair.
This implies that the point c and the point d are
connected to the point a and the point b. Because of
the strategy used in this game. This creates 2 K3, so
either the game is lost by the losing player, or no
poisoned pairs are formed
Proof
Theorem: Play between two unconnected pairs with the strategy for this
game will always result in either no poisoned pairs being formed or 2
poisoned pairs being formed.
Proof:
Case 1: Assume the pair {a,b} and {c,d} being played between have not been
played between before.
If the losing player connects a to c, then the winning player connects b to
d or if a is connected to d, then b is connected to c. In either case, no
change is made to the state of the pairs {a,b} or {b,c} so no poisoned pair
is formed.
Case 2: Assume that the pair {a,b} and {c,d} have been played between
before.
This implies that after the next round of playing, the points will be
connected so that a and b are connected to both c and d. This implies that
the pair {a,b} is a poisoned pair and that {c,d} is also a poisoned pair.
Therefore two poisoned pairs were formed.
Proof
• All of those proofs show that so long as play between
poisoned and unconnected pairs cannot happen, there
will be an even number of poisoned pairs.
• Since the winning strategy has a response to any move
between pairs, then the deciding move is based off of
the number of unconnected pairs, which for the winner
will always be an even number after there turn since
there will eventually be 0 unconnected pairs after their
turn.
• The rules of this game version can be forced into the
original game on games of size 4,6,and 8 by the moves
one of the players makes.
Proof
• Since an even number of poisoned pairs will
be formed in a game, the winning player will
be the 2nd player if the number of
unconnected pairs is divisible by 2, and the 1st
player will win otherwise.
• This leads to the 2nd player wining on games of
size 4,8 and the 1st player winning on a game
of size 6.
Final Results
• I could not prove who would win any of the original game
except on graphs of size 4,6,and 8.
• I did create a script using a program called magma which
solved for the winner of the game using brute force methods,
and these were the results:
Graph 3 4 5 6 7 8 9 10 11
Size
Winning 2 2 2 1 2 2 2 1 2
Player
• I could only get to graphs of size 11 because the number of
possible moves in a game grew extremely quickly.
Final Results
Graph 3 4 5 6 7 8 9 10 11
Size
Winning 2 2 2 1 2 2 2 1 2
Player
This table suggests that the 1st player will only
win on number satisfying n = 2m+2.
I believe that this pattern will continue, but have
not found a way to prove that conjecture.
Acknowledgements
Jason Williford – my research advisor
Wyoming Epscor
Any Questions