Strategies in the Game F-Saturator

In mathematics, a graph is a set of vertices and a set of edges which connect pairs of vertices. A subgraph is graph that is a subset of vertices of a graph and a subset of the edges connecting those vertices. Some example graphs can be made drawing dots (vertices) on a piece of paper and drawing lines (edges) between those dots. Let F be a graph. The game F-Saturator is played by two players who take turns adding edges to a graph G. A player loses if after their move, F is a subgraph of G. For example, a triangle could be F, and if a player adds an edge which completes a triangle, that player loses. This game is a tool to increase understanding of F-saturated graphs. An F-saturated graph is a graph which does not contain some subgraph F, but the addition of any edge to that graph creates the subgraph F. In this presentation, I analyze some versions of F-Saturator to determine which player wins and discuss the challenges of determining the winner through brute force computation.