Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
5
votes
1answer
467 views

Find how many colors are needed to color all vertices

In this puzzle you need to identify the minimum number of colors needed to color vertices such that no two adjacent vertices ...
6
votes
1answer
157 views

Finding the most flexible of all 35 hexominoes

Of all 35 hexominoes, which is (or are) the most flexible of all, that is, the one (or ones) that can be converted into the most other hexominoes just by cutting out one of its component squares (thus ...
2
votes
1answer
85 views

Happy Birthday, Don!

My friend Johan de Ruiter has made a nice puzzle for Donald Knuth's Birthday. The numbers indicate how many connections that candle has. Can you solve it? Original link: https://www-cs-faculty....
19
votes
1answer
986 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 ...
4
votes
1answer
132 views

Playing Collatz with graphs

a) Given a set of positive integers, its common divisor graph (CD-graph) is the graph whose vertices are the integers, two of which are joined by an edge if (and only if) they have a common divisor ...
17
votes
2answers
613 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 ...
9
votes
1answer
292 views

A Demetri Puzzle

Apparently, yesterday was National Puzzle Day (in the US, I think). As part of the celebration, American comedian Demetri Martin posted a puzzle on Twitter: https://twitter.com/DemetriMartin/status/...
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 ...
4
votes
1answer
130 views

Another series of fortunate (and sideways) 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
389 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 ...
7
votes
1answer
150 views

Given a 7x7 grid, what moves need to be made to get two agents on their respective opposite sides of the grid on the diagonal?

Say I had the following 7x7 grid and two agents on the grid facing one another as shown. The agents can follow the following commands: moveForward, turnRight, turnLeft. The agents have to follow the ...
12
votes
2answers
485 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 ...
13
votes
2answers
277 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 ...
5
votes
1answer
142 views

The grandest zoo in Appelhaken

In the magnificent country of Appelhaken there is a zoo. Not just any zoo, but a grand zoo, a magnificent zoo, called Appelhaken Grand Magnificent Magnificent Grand Grand Zoo. In this zoo there are ...
8
votes
1answer
169 views

The grandest bridge in Appelhaken [duplicate]

In the capital of the grand country of Appelhaken there is a plane garden containing four magnificent monuments. So magnificent are they that the country has a Law requiring that there must be a ...
2
votes
3answers
155 views

Problems on Graphs

I want to test if someone with no experience in Graph Theory can solve my Problems involving Graphs. If you do know some Graph Theory I'd appreciate if you let me know in your answer. They do not ...
0
votes
2answers
109 views

Painting edges of a 3x3 grid with 4 colours

Can you paint the edges of a 3x3 grid with 4 colours, such that: The colours of edges of every 1x1 square are different. The colours of edges adjacent to every vertex are different. Here is a ...
0
votes
1answer
69 views

Painting edges of a 2x2 grid with 4 colours

Can you paint the edges of a 2x2 grid with 4 colours, such that: The colours of edges of every 1x1 square are different. The colours of edges adjacent to every vertex are different. Good luck!
9
votes
1answer
505 views

Connect the wires without setting off the bomb

You just saw a planted time bomb! Just 5 minutes are remaining until it explodes and as you are in currently in a rural area (no bomb disposal squad) and you know how bombs usually work it is up to ...
8
votes
1answer
559 views

Winning the Lottery

Bob: I hear you won the lottery. Alice: So I did! Bob: What six numbers did you win it with? Alice: Can't remember. All I recall is that they were all different, and none greater than 28. Bob: ...
10
votes
2answers
559 views

National Graph Lottery

In UK's National Lottery players choose 6 different whole numbers in the range 1 to 59, and win a large prize if all six match with the day's draw. Each choice of six numbers by a player gives rise ...
12
votes
1answer
414 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 ...
10
votes
2answers
594 views

A Magic Flying Saucer

Place 19 different positive integers on the vertices of this graph so that the 13 products of three numbers in a straight line are all equal. Do so in such a way that the product is as small as ...
5
votes
1answer
215 views

Uncover Lenny Fingers' street hustle

Lenny Fingers is out on the street again, hustling people with his shell games. This time, he's using words. As you walk by, Lenny grabs you with an enthusiastic smile and shows you two words side-...
15
votes
1answer
337 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 ...
7
votes
1answer
195 views

Stars of the Celestial Bagua

Check this out: Okay, it might be more impressive if I show you what is moving along the arrows: At every vertex in a long word. Flowing in to every vertex are two short words ("inputs"). ...
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 ...
10
votes
4answers
334 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 (...
4
votes
1answer
236 views

London Underground puzzle

This is something I have thought about during my commute through the London Underground. Is it possible to make a trip through the London underground in such a way that: You have to use all ...
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 ...
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 ...
-1
votes
2answers
119 views

Can this be drawn in one line without going over the line?

Can this image be drawn in one line and without going over any lines?
17
votes
2answers
529 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 ...
6
votes
7answers
323 views

Find minimum number of meeting periods to reach 2 degrees of separation for a group [closed]

I am running a training course and I want to arrange a set of 1:1 meeting periods between the participants such that at the end of the day there is a maximum of 2 degrees of separation between any of ...
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 ...
4
votes
2answers
165 views

Identify this type of graph puzzle

There are $V-1$ pieces, each with an identifying symbol. The board is a graph with $V$ vertices and some number of edges $E$. The idea is to move around the pieces so that each piece's symbol matches ...
0
votes
1answer
120 views

A Colorful Honeycomb

What strategy can you use to color using only 6 colors the lines in an infinite hexagonal tiling such that no two sides of the same hexagon have the same color?
11
votes
6answers
738 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 ...
3
votes
1answer
215 views

Create a map of a game's portals

Given a set of rooms, each with a N, a S, an E, and a W exit/entrance to another of the rooms, create as simple a map as possible that graphically represents their connections. The rooms in question ...
-4
votes
1answer
365 views

A party of jealous guys

I was really happy for the fact that I won the inter-galactic best magician award. So I decided to throw a party of $n$ people (excluding me). The people who came to that party was jealous, really ...
22
votes
1answer
763 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 ...
17
votes
1answer
506 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. ...
14
votes
3answers
381 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 ...
11
votes
1answer
496 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 ...
4
votes
2answers
261 views

How many nodes in the network?

I don't actually have a solution in mind for these, but it seemed puzzly enough to bring to the table. Seems as though someone must have come up with this before, but if so, I couldn't find it when I ...
5
votes
3answers
601 views

Magic-preserving Permutations on a 4x4 Magic Square

Messing around with some magic-square puzzles, I faced the problem of deciding whether some two magical squares are, in fact, the one and same square wearing a different hat. It seemed to me, that for ...
7
votes
2answers
214 views

A partition of 1000 into six parts with least and greatest product possible

Find six positive natural numbers, not necessarily distinct, whose sum is 1000 and which, if placed appropriately on the vertices of the following graph, two of them will be joined by an edge if and ...
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 ...
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 ...
1
vote
1answer
269 views

Scheduling Meetings

I came across this problem in real life and thought it could be made into an interesting puzzle. I will enjoy seeing how my eventual solution could be improved! Here's the situation. There ...