# 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.

159 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. ...
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 ...
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 ...
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....
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?
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, ..., ...
6k 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 ...
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 ...
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 ...
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?...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
1k views

### What node does 11 point to?

If we included 11 in the diagram below, which node would it connect to? Hint 1
345 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 ...
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 ...
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?
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 ...
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 ...
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:
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
953 views

...
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 ...
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 ...
429 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: ...
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. ...
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 ...
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 ...
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 ...