Questions tagged [graph-theory]

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

97 questions
Filter by
Sorted by
Tagged with
32 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 ...
186 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-...
314 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 ...
184 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"). ...
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 ...
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 ...
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 (...
215 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 ...
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 ...
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 ...
506 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 ...
112 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?
599 views

The governor of Reniets (a land far, far away!) is known to be very stingy. He has to build a road which connects all the five cities in the region, which are oddly arranged on the vertices of a ...
317 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 ...
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....
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 ...
127 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 ...
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?
117 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?
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 ...
211 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 ...
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 ...
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. ...
738 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 ...
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 ...
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 ...
243 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 ...
396 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 ...
205 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 ...
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 ...
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 ...
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 ...
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 ...
183 views

Triangle of Safety

Saitama: "The Hero Association called me for a low-level mission, can you meet them as my representative?" Genos: "No." Saitama: "Aww, man.. That's not fun." Then Saitama decided to meet Hero ...
186 views

Trip Routes that Visit 9 of 10 Cities

There are 10 cities on this island. For each pair of cities, they may have a bidirectional path. A trip route is defined as a route which start on a city e.g. $A$, goes to 8 of 9 other cities exactly ...
309 views

A certain partition of 130

Given a multiset of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than ...
231 views

Teacup geometry

Inspired by the three utilities puzzle from prog_SAHIL I'm now posting a similar puzzle that makes use of the topology of a cup with a handle: The question is: How many distinct points can you ...
176 views

A minor rearrangement of the one sided hexominoes in 12 simultaneous shapes

Here are the one sided hexominoes arranged into 12 congruent shapes. But there are one or two flaws: The dark blue hexominoes, which are the symmetric ones, may not occur more than once each in a ...
354 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 ...
893 views

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 ...
2k views

Color this map using only 4 colors (easy)

According to graph theory, in order to color any map so that 2 touching regions don't have the same color, 4 distinct colors are enough. Can somebody color the following map?
1k views

Is there a simple algorithm for solving Kami 2 puzzles?

I'm finding my life has been consumed by Kami 2, partly because I seem to have achieved some "insight" and am able to solve the puzzles reliably, almost always on the first try. The rules are simple: ...
365 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 ...