Questions tagged [graph-theory]

A puzzle built around graphs: sets of nodes joined together by paths.

Filter by
Sorted by
Tagged with
16
votes
4answers
11k 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 ...
31
votes
18answers
29k 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....
9
votes
6answers
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. ...
14
votes
3answers
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 ...
41
votes
1answer
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. ...
35
votes
11answers
19k 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 ...
7
votes
3answers
895 views

Spreading Gossip

Initially, each of 50 Puzzling Stack Exchange users have a single distinct juicy bit of gossip not known to the others. If $A$ sends an email to $B$, that email can include all the bits of gossip $...
24
votes
5answers
2k views

Superhero words!

Quietly walking among us are words which are actually superheroes in disguise! Just as Diana Prince spins around to become Wonder Woman, some seemingly ordinary words can spin around to reveal their ...
16
votes
5answers
773 views

Maximize the number of paths

You have exactly 990 edges. Assemble them into a simple undirected graph with two distinguished vertices A and B, such that the number of different simple paths from A to B is as large as you can make ...
14
votes
2answers
359 views

Hexominoes into 7 simultaneous congruent shapes

I came up with this puzzle 16 years ago, it was on Ed Pegg's Mathpuzzle site but nobody solved it AFAIK. The 35 hexominoes (which look like this): are to be arranged, in groups of five, into seven ...
11
votes
1answer
374 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 ...
9
votes
6answers
1k views

A closed path on the Rubik's cube

Is it possible to draw a closed path on the surface of a standard $3\times3\times3$ Rubik's cube such that the path traverses each of the $54$ little squares exactly once, and such that the path ...
23
votes
7answers
5k views

Hacking an electronic keypad

You are a spy trying to break into an enemy facility. The back door is protected by an electronic keypad lock. You know that this particular lock is opened by a four digit code. Any stream of button ...
12
votes
5answers
1k views

Soccer balls in the stadium

The coach asks you take as many soccer balls as possible and put those balls onto the field with the condition that For any arbitrary set of three balls, at least two of those balls are exactly 10 ...
10
votes
2answers
846 views

Dissecting a square

You are asked to dissect an $N \times N$ square into polyomino pieces such that each piece shares portion of its boundary with exactly $D$ other pieces, and no piece has area exceeding $N$. This can ...
8
votes
1answer
421 views

A perfect metro map

You are working for a company and asked to create a perfect metro map where there will be as many stops as possible. But there are two constraints which limits the number of tracks (railroads) and ...
6
votes
3answers
1k views

A party puzzler

At a party, everybody is friend with exactly $22$ of the other persons present. Whenever two persons are friends, they do not have any friends in common. Whenever two persons are not friends, they ...
10
votes
2answers
520 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-...
10
votes
1answer
492 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 ...
23
votes
5answers
6k 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?
5
votes
1answer
242 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 ...
4
votes
2answers
198 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 ...