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.

Filter by
Sorted by
Tagged with
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. ...
36
votes
11answers
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 ...
34
votes
7answers
7k views

Why is it impossible to connect 3 black dots to 3 red dots?

Connect each red circle with each black circle by drawing a line and the lines should not touch. From each red circle, 3 lines must be drawn which connect red circles with black circles, but the lines ...
32
votes
18answers
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....
27
votes
5answers
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?
26
votes
3answers
852 views

Ever increasing highway numbers

A province has 10 cities (arranged in a circular manner). Every pair of cities is directly connected by a straight highway, and each has its own unique number: Highway 1, Highway 2, Highway 3, ..., ...
24
votes
7answers
6k 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 ...
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 ...
23
votes
1answer
798 views

A Tour Around a Triangle

Place the 18 even integers between 2 and 36 in the empty nodes of this triangular graph in such a way that if a path is drawn by coloring in red all the edges joining any two nodes whose numbers add ...
22
votes
1answer
571 views

New Year Graph Puzzle

In the graph below, each node is coloured either red or yellow, except for the white node in the bottom left, which I've marked with an X. Can you tell me what the white node marked with X represents?...
21
votes
2answers
3k views

Help the prisoners

Given a 5×5×5 cube of identical cubical cells (total 125 cells). In each cell there is a prisoner. There are doors from each cell to the adjacent cells (not diagonally). Their task is to ...
20
votes
1answer
1k views

Four mathematicians and their ages

Four mathematicians, none yet a centenarian, meet for coffee. The graph-theorist among them noticed that the common divisor graph of their ages (that is, the graph whose vertices are their ages, two ...
20
votes
2answers
812 views

Honeydripping around the clock

      What path could a honeybee follow, beginning and ending at top center, visiting every empty cell exactly once and dripping 2 drops of honey into the last cell? Start ...
19
votes
3answers
3k views

School where every pair of students share a common grandfather

There are $64$ pupils attending a particular school. Any two of these pupils share (at least) one common grandfather. Does this imply that there are at least $43$ pupils all of which have a common ...
19
votes
3answers
3k views

A rook's tour of the chessboard

Place numbers 1 to 64 in the cells of this 8 x 8 board in such a way that consecutive numbers, and also numbers 1 and 64, occupy neighboring cells (either vertically or horizontally). Shaded cells ...
18
votes
2answers
632 views

Another Rook's Tour

Place numbers 1 to 100 in the cells of this 10 x 10 board in such a way that consecutive numbers, and also numbers 1 and 100, occupy neighboring cells (either vertically or horizontally). Prime ...
18
votes
1answer
432 views

Interconnectivity

As I was walking through my university's mathematics department, I came across a poster pinned to the notice board. Underneath, it simply said 'In memory'. However, I could not connect the poster to ...
18
votes
6answers
1k views

The Islanders and their Birthday Presents

Once upon a time, a band of colonists, all having distinct birthdays, settled on a remote island. They had brought some mementos from the old country, around which certain mores regarding friendships ...
18
votes
1answer
527 views

A partition of 1000 into nine parts

The sum of nine whole numbers is 1000. If those numbers are placed on the vertices of this graph, two of them will be joined by an edge if and only if they have a common divisor greater than 1 (i.e. ...
17
votes
2answers
2k views

Professor Halfbrain and the fantasy knight

Professor Halfbrain owns a $99\times99$ board for fantasy chess, whose rows are numbered consecutively from $1$ to $99$ and whose columns are also numbered consecutively from $1$ to $99$. A fantasy ...
17
votes
4answers
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 ...
17
votes
3answers
2k views

A partition of 100 into nine parts

The sum of $9$ positive natural numbers, not necessarily distinct, is $100$. If placed appropriately on the vertices of the following graph, two of them will be joined by an edge if and only if they ...
17
votes
2answers
561 views

Maximum Height of a Hotel with Strange Elevators

I encountered this puzzle many years ago, and I think back on it often as it is unique and thought provoking. As far as I know nobody has proved the given solution as optimum, so it may still be ...
16
votes
5answers
834 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 ...
16
votes
1answer
1k views

What node does 11 point to?

If we included 11 in the diagram below, which node would it connect to? Hint 1
15
votes
1answer
345 views

Newton's cradles

I went to one of those discovery stores and picked up a few Newton's cradles, except these have hanging words instead of hanging spheres. Check it out: This one has a starter pendulum with two ...
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 ...
14
votes
4answers
2k views

Touching coins flat on a table

On an infinite table are $n$ identical circular coins lying flat. Each coin touches exactly $k$ other coins, and any two coins are connected by a path of touching coins. Determine all possible pairs ...
14
votes
5answers
558 views

To each his own

You are a graduate student in theoretical mathematics, dabbling every so often in some interesting but equally useless computer science theory. From the beginning of the year, Professor Carl Hayden ...
14
votes
1answer
810 views

Touring the United States

You need to find a continuous path within the US that passes through all 48 contiguous states, visiting each one exactly once. If you start in Delaware, which state do you end in?
14
votes
2answers
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 ...
14
votes
2answers
406 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 ...
14
votes
1answer
394 views

Currency connections

Two Forex traders are trying to communicate about their trades. They send each other images with a hidden meaning like this one: Can you work out which currencies they are trading? Hint:
14
votes
1answer
1k views

A chic party puzzler

(Based on this puzzle by Gamow. The answer there might give you a hint (so don't look yet!)) At a fancy party in Café la Tour, everybody is friends with exactly 14 of the other people present. ...
14
votes
3answers
394 views

Fearful asymmetry

An asymmetric graph (or identity graph) has every vertex unique: no different relabeling of the vertices leaves the edges unchanged. The trivial graph on one vertex is (trivially) asymmetric. All ...
14
votes
2answers
299 views

Happy birthday Ramanujan!

On December 22 2019, Ramanujan would have been 132 years old. In his memory here are two puzzles around 132. In the six vertices of each of these graphs place six positive integers that add up to ...
13
votes
1answer
1k views

Primes in a Diamond

Label the vertices of this graph with numbers 1 to 16 in such a way that the edges between any two vertices whose sum and absolute difference are both primes are precisely the edges of a hamiltonian ...
13
votes
1answer
1k views

Hunter chasing a fox on a graph

This is a variant of the sleeping princess puzzle. There are fifteen foxholes, connected by underground tunnels as shown below. A fox is sleeping in one of them. Every day, a hunter checks one of ...
13
votes
1answer
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 ...
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 ...
12
votes
4answers
953 views

The Duplicator and the Safe

...
12
votes
2answers
2k views

My Graph Theory Students

I have 18 students in my graph theory course this semester: Anne, Bernard, Clare, David,..., and Rachel. At the start of the course I asked them to draw the graph below, in which each of them is ...
12
votes
2answers
500 views

Heavens to Megatron!

See if you can fill in all the blank letter tiles in this graph using the clues sets below. Each set of clues yields a name or word. The name or word is guaranteed to follow some connected path ...
12
votes
5answers
429 views

Twitter Followers

There is a group of 300 Twitter users. Each user is following exactly one other user in the group. Prove that there exists a smaller group of 100 users where no one is following anyone else. Source: ...
12
votes
1answer
318 views

Multibranched tree

The Furca Fractalis tree grows in a very special way. Starting with the trunk there are three possibilities to continue growing: It can split in two branches. It can grow one branch and one leaf. ...
12
votes
1answer
392 views

Jigsaw Logic: ?s galore

I am working on a 256 piece jigsaw puzzle, but I am having a lot of trouble. Instead of the picture being a landscape or painting, the final image is just a sixteen by sixteen grid of identical ...
12
votes
1answer
363 views

Infection (Information Dissemination) Puzzle

There are 2020 people in a room. One person has COVID. After each minute, each person $\mathrm{P}$ is paired with some other person $\mathrm{Q}$ who was never paired with $\mathrm{P}$ before, and they ...
11
votes
5answers
777 views

Can the idiot's route be less expensive than the genius' route?

In a certain country, there are $n$ cities. Between every pair of cities, there is a fixed travel cost to go from one city to the other. An idiot and a genius both decide to tour this country by ...
11
votes
6answers
775 views

I Have To Be With Them!

It's almost time for another year of school! But before school starts, Principal Little needs to form classes. Because there are so many people in a class, the parents are always complaining, asking ...
11
votes
1answer
308 views

Gaby´s Puzzle (Primes Around a Circle)

To keep them busy during lockdown, Gaby asked her children to find a way to place the first sixteen primes (2 to 53) around a circle so that either the sum or difference (or both) of any two of them ...