Actually playable games based on graphs? In computer science lessons, we have recently got the task to program something using graphs. Due to my enthusiasm for computer games, i would really prefer to implement a concept for a game. The requirements for the project are:


*

*the underlying graph mustn't be necessarily planar and it would be better if it's not necessarily plain, too (so you can't simply implement tic-tac-toe for example)

*the underlying concept shouldn't be too hard to understand

*the game should be enjoyable to some extend

*it should be a one-player game


(but only the first requirement is really necessary)
So does anyone have an idea? I'm very grateful about any proposal!
 A: The game of Sim is very playable and is pure graph theory.  The board consists of six dots. Two players, Red and Blue, take turns; a player's turn consists of  picking two points that are not already connected with a line, and connecting them with a line of that player's color.  A player who completes a triangle of their own color loses.
A famous theorem of Ramsey theory states that the game of Sim cannot end in a tie; after 15 half-moves, the board is full and must contain a triangle of one player's color. (If the game is played on a board with only five dots, it can end in a tie.)
A: You asked for one-player games; here's one: Planarity.  The game presents a planar graph, and the player's job is to find a planar embedding of the graph by rearranging its vertices.
A: Here is an Android game I made inspired by Hamilton's Icosian game, where you must connect every node by visiting them only once. I used Mathematica to generate planar graphs that have only one solution, and then a custom software to turn the graph into a map by representing nodes as regions (or "villages") and edges as borders between regions.
The first few levels are pretty easy but it gets harder as you progress, although I unfortunately hit a limit on the number of "regions" you can fit inside a phone screen. 
A: Though I question the on-topicness of this question, how about 9 men's morris?
I love this game and used to play it all the time. It's also generalizable to $n$ men's morris on various sized boards which might be interesting.
A: Maybe not what you are searching, but very interesting: the game Sprouts.

The game starts by drawing three dots.

...

The first player has a turn by joining two of the dots and marking a new dot in the middle of the line. Or the line may start and end on the same dot.

...

When drawing a line, it cannot cross another line. (This is important to remember!)
A dot cannot have more than three lines branching to or from it.

...

A: Here is an interesting game, note that you can replace the hexagon with any other $n$-gon, you just need to keep two nodes on each of its edges with only one edge being connected to each node inside 1 $n$-gon. You can also make other generalizations etc.
http://entanglement.gopherwoodstudios.com/en-US-index.html
