# Questions tagged [graph-theory]

A puzzle built around graphs: sets of nodes joined together by paths. General graph theory questions are off-topic but can be asked on Mathematics Stack Exchange using the [graph-theory] tag.

34 questions
Filter by
Sorted by
Tagged with
15k views

### Drawing something using one pen stroke

Can you determine if it's possible to draw a geometric figure (made up from shapes like rectangles, triangles, and other regular shapes) with one pen stroke and not drawing the same line twice. I am ...
49k views

### Draw a line through all doors

I saw the following problem on 4chan and couldn't solve it: It's very likely to be some kind of troll (no solution). I'm hoping to see some rigorous proofs that disprove the existence of such a line....
2k views

### The Bunny's Tour

The Bunny is a new chess piece. It can move in 2 different ways: Diagonally, but only exactly one space (so like a bishop with the limitations of a king). It can also "Bunny-Hop" over another bunny. ...
1k views

### Touching Matchsticks

You are asked to place matchsticks on a flat surface such that each matchstick end meets three others, and no matches cross. It is easy to achieve this for patterns that extend indefintely: The ...
3k views

### Crippled King Crossing a Canyon

A chess king has been injured in battle against an evil wizard, and can no longer move northeast or southwest. This king is on the North rim of a canyon, and must flee to safety on the South rim. ...
22k views

### Connect 3 houses with 3 wells

Connect every house with every well without the lines intersecting. I am not sure if this puzzle has a solution. I have been puzzled by it for a long long time. An old man from my village mentioned ...
1k views

### What node does 11 point to?

If we included 11 in the diagram below, which node would it connect to? Hint 1
312 views

### Teacup geometry

Inspired by the three utilities puzzle from prog_SAHIL I'm now posting a similar puzzle that makes use of the topology of a cup with a handle: The question is: How many distinct points can you ...
8k views

### Is there a proof that a map of the United States requires 4 colors?

The Four color theorem states that no more than four colors are required for any map. Can it be proved or disproved that 3 colors can be used for United States map?
916 views

401 views

### A series of fortunate transpositions

Using only a sequence of transpositions, see if you can take this: to this: while maintaining English words on each of the three horizontals. At each step, you may transpose any two neighboring ...
440 views

### The arrow of time flies in reverse

Here is the puzzle: (Click on the image to see a larger image.) Overview: This is a word graph. The nodes are short words, the edges are long words. Whenever an edge (i.e., a long word) connects ...
504 views

### Labelling a graph with a partition of 100

Label the vertices of this graph with positive integers (repetitions allowed) whose sum is 100 in such a way that any pair of vertices are joined by an edge if (and only if) they have labels with a ...
528 views

### Lost in Gnu York

Wanda the Wanderer is driving the streets of Gnu York. She doesn't know the what the entire map of Gnu York looks like, but she knows this much: Gnu York is flat Every intersection of streets is four-...
214 views

### Phone pattern security

My phone is unlocked using a security pattern. This is a path drawn through a 3x3 grid of dots with the following rules: The path can start at any dot The path visits neighbouring dots: horizontally,...
119 views

### Name that node #1 (Beginner's Level Puzzle)

While Puzzling.SE has some extremely clever and difficult puzzles that are being solved by people whose intellect amazes me, I wanted to make some graph puzzles that were specifically meant for ...
143 views

### Another series of fortunate (and sideways) transpositions

Using only a sequence of transpositions, see if you can take this: to this: while maintaining English words on each of the three horizontals. At each step, you may transpose any two neighboring ...
480 views

### Which node(s) does 16 connect with in this simple graph?

If we add 16 as a node to the graph below, which node(s) will it connect to? Hint 1 Hint 2 Hint 3 Hint 4 Hint 5
174 views

### The grandest bridge in Appelhaken [duplicate]

In the capital of the grand country of Appelhaken there is a plane garden containing four magnificent monuments. So magnificent are they that the country has a Law requiring that there must be a ...
388 views

### Primes in a Line

Place the first 20 primes (2 to 71) in a line so that the sum or difference (or both) of any two primes that find themselves next to each other is always a perfect square. For which other values of N ...
254 views

### MPire coloring game basic strategy

The MPire coloring game is a game where several "empires" are laid out touching each other. Your task is to color each empire a different color, and not let two of the same color touch. You also have ...
229 views

### What's the graph relation? #3

What's the relation that joins the nodes? Previous What's the graph relation? #1 What's the graph relation? #2
234 views

### Four mutually adjacent US states (not the Four Corners) [closed]

The question Is there a proof that a map of the United States requires 4 colors? was answered by showing that Nevada has five neighbors, each adjacent to the next (an "odd wheel"). "Adjacent" here ...