Questions tagged [graph-theory]

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

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. ...
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 ...
31
votes
18answers
28k 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....
26
votes
3answers
814 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
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
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 ...
23
votes
5answers
5k 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?
22
votes
1answer
736 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 ...
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
2answers
761 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 ...
18
votes
1answer
404 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 ...
17
votes
2answers
505 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 ...
17
votes
1answer
493 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. ...
16
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 ...
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 ...
16
votes
5answers
770 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
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 ...
15
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 ...
15
votes
1answer
307 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
522 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
2answers
353 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
987 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
372 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 ...
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
786 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?
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
935 views

The Duplicator and the Safe

...
12
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 ...
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
5answers
424 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
290 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
352 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 ...
11
votes
5answers
757 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
717 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
458 views

Any hope for Humpty Dumpty?

It was inevitable, really... Each fragment of shell has exactly three sharp points, joined by smooth curves. While the King's horses can count reasonably well, his men have been known to confuse ...
10
votes
4answers
307 views

Choo-choo! Word trains

All aboard the Word Train Express! Engineering a word train is simple: I'll give you the locomotive (the first word) and the caboose (the last word), and I'll specify the number of boxcars (...
10
votes
2answers
1k views

An old square castle with many square rooms

The grandfather of my friend Bob has built a perfect square castle for himself and his family and divided it into 9 perfect square halls and made an armoury in the middle one. Bob's father divided ...
10
votes
5answers
810 views

Houses in a grid

You are a city planner tasked with the placement of unit-square-sized houses in a rectangular-grid allotment, the size of which is up to you but must be as small as possible to save money. The number ...
10
votes
1answer
1k views

How many colors does it take?

This question is from a popular monthly science magazine in my country: You have an 8x8 square where any 3 squares forming a tromino (including reflections and rotations) must consist of three ...
10
votes
2answers
517 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
485 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 ...
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 ...
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. ...
9
votes
4answers
447 views

Mystery on the trail to Dutch Flat

On a recent amble, I happened upon a sign $\small \raise2mu ( {\normalsize\sf\color{#d90} A} \raise2mu )$ that seemed to indicate a mistake — or— a mystery. ...
9
votes
2answers
834 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 ...
9
votes
1answer
413 views

Generalisation of tours on chessboards

It's well-known that a knight placed on one square of a chessboard can get to any other square, but a bishop can only reach half the squares from a fixed starting point. Another question on this site ...
9
votes
2answers
364 views

Looking for another partition of 100

The sum of ten, not necessarily different, positive integers is 100. If placed adequately on the vertices of this graph, two of them will be joined by a line if, and only if, they have a common ...