# Questions tagged [graph-theory]

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

96 questions
Filter by
Sorted by
Tagged with
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. ...
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 ...
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....
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, ..., ...
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 ...
5k views

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 ...
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?
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 ...
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 ...
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 ...
405 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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
771 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 ...
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 ...
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 ...
313 views

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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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?
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 ...
935 views

...
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 ...
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 ...
424 views

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: ...
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. ...
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 ...
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 ...
718 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 ...
459 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 ...
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 (...
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 ...
811 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 ...
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 ...
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-...
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 ...
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 ...
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. ...
449 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. ...
835 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 ...