Puzzling

Questions tagged [graph-theory]

Ask Question

A puzzle built around graphs: sets of nodes joined together by paths. Use with [mathematics]

166 questions
Newest
Active
Bountied
Unanswered
Filter by
Sorted by
Tagged with
0
votes
1answer
85 views

Trail passing through squares of a grid

Let's construct a 10x10 grid. 0n the 100 squares you are allowed to place 7 bases (the red dots in the diagram below) in any square on the grid. Then you fill the grid with skinny trominoes. The ...
3
votes
2answers
197 views

Pirates dividing booty around a circular table

A group of pirates have plundered one of his majesty's cargo ships and they all carried as much gold coins as each one could find. When they get back to their ship, they sit at a round table and pass ...
2
votes
0answers
68 views

Fair and square island hopping [duplicate]

If amateur fiction is not your thing skip to the bottom. As IP (Implausible Physics) expert for DREAM, the Department for Reckless Engineering and Advanced Megalomania you have been tasked by sheikh ...
1
vote
2answers
228 views

Minimize the longest King chain on a 6x6 ternary grid

This puzzle is an extension of this one: Minimize the longest King chain on a 5x5 binary board Given a grid filled with numbers, we define a King chain to be a path on the grid such that: The path ...
0
votes
1answer
125 views

Minimize the longest King chain on a 7x7 binary grid

This puzzle is an extension of this one: Minimize the longest King chain on a 5x5 binary board Given a grid filled with numbers, we define a King chain to be a path on the grid such that: The path ...
13
votes
7answers
838 views

Minimize the longest King chain on a 5x5 binary board

Given a grid filled with numbers, let's define a King chain to be a path on the grid such that the path can be traversed with chess King's moves (moving to one of 8 adjacent cells at a time), the ...
0
votes
1answer
97 views

Gaby's 21 students sitting around a circle [closed]

Gaby numbers her 21 students with the primes between 11 and 97. She now asks them to sit around a circle making sure that any two of them sitting next to each other have either their tens or units ...
2
votes
1answer
148 views

My sixteen graph theory students

I will have sixteen students in my graph theory course this semester. In our first session I asked each of them with which of the other 15 students in the class they were already acquainted before the ...
3
votes
0answers
194 views

Infected Cylinder and Torus

A variant of the well known Infected Checkerboard problem. If we've a 𝑛x𝑛 square, then we fold it along top and bottom row to form a cylinder. A cell in this cylinder becomes infected if at least ...
1
vote
1answer
83 views

Painting a plane!

Paint the points on a plane with three colors, so that the points on each line are a maximum of 2 colors, and all three colors are used. (Math Festival 1990)
4
votes
1answer
162 views

Visiting streets, not houses

The section points are houses and lines are streets, all with one unit length. What is the fewest number of units you must travel to visit every street at least once?
22
votes
1answer
593 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?...
0
votes
2answers
74 views

Show that no lines need cross [closed]

There are n red points and n blue points in the plane. Show that you can always join all the red and blue points with straight lines so that no two lines cross. Each point can have exactly one line ...
14
votes
1answer
405 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:
7
votes
2answers
826 views

Frog game on a dandelion graph

There is some noise in the local pond. A group of frogs wants to host a birthday party! There is a total of 22 lily pads in the pond, each housing a single frog. They are labelled as numbers from 0 to ...
9
votes
2answers
472 views

Dragon summoning spell

The parchment shown below got stained with something. See if you can determine the obscured parts.
7
votes
1answer
169 views

Four color a map - but go light on the fourth color!

Here's a map, which I found here: Your challenge is to four-color this map while minimizing your use of the fourth color. More specifically, color the map with four colors so each region is a ...
3
votes
1answer
84 views

How many different ways can you color the diagram?

This question is a continuation of this one. Here are nine squares, connected by lines. Each square must be colored, and two squares connected by a line must be colored differently. Question 1. What ...
12
votes
1answer
366 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 ...
2
votes
0answers
455 views

A robot moving on a grid. Part 2

This is an extension of the discussion A robot is placed on a grid point. At each move the robot must take three steps along the edge of the grid. After each step the robot must turn right. Lengths of ...
2
votes
1answer
248 views

A robot moving on a grid

In the spirit the question I propose the puzzle: A robot is placed on a vertex of a grid. At each move the robot must take three steps along the edge of the grid. After each step the robot must turn ...
5
votes
2answers
346 views

Seventeen positive integers

Find 17 positive integers such that no four of them have, pairwise, a common divisor greater than 1, but, likewise, no four of them are, pairwise, relatively prime. Do so in such a way that the ...
5
votes
1answer
98 views

The sandpiles on the beach

We call a convex polyhedron a sandpile if one of the faces, called base, has a common edge with all the other faces. Furthermore, each vertex is linked with three edges. We consider the sandpiles by ...
1
vote
2answers
167 views

LGBT+ SpeedDating

Congratulations! You are now the lucky franchise owner of 'SpeedDating Inc'. We are the number one organiser of speed-dating events in WhereverYouAre. We would love for you to start organizing new ...
7
votes
2answers
216 views

Phone pattern security

My phone is unlocked using a security pattern. This is a path drawn through a 3x3 grid of dots with the following rules: The path can start at any dot The path visits neighbouring dots: horizontally,...
8
votes
2answers
173 views

Intersecting shapes on a flat surface

What is the maximum number of enclosed regions that you can create by drawing two circles and two triangles on a flat surface? Try answering with mathematical arguments.
10
votes
4answers
804 views

Draw this planar graph

The playing board for this puzzle is a short list of digits; there is one rule governing possible moves: The 1 may swap with a digit one place to the right; the <...
11
votes
1answer
312 views

Gaby´s Puzzle (Primes Around a Circle)

To keep them busy during lockdown, Gaby asked her children to find a way to place the first sixteen primes (2 to 53) around a circle so that either the sum or difference (or both) of any two of them ...
2
votes
1answer
94 views

What's the graph relation? #4

What's the relation that joins the nodes? Previous What's the graph relation? #1 What's the graph relation? #2 What's the graph relation? #3
4
votes
1answer
231 views

What's the graph relation? #3

What's the relation that joins the nodes? Previous What's the graph relation? #1 What's the graph relation? #2
6
votes
2answers
388 views

Primes in a Line

Place the first 20 primes (2 to 71) in a line so that the sum or difference (or both) of any two primes that find themselves next to each other is always a perfect square. For which other values of N ...
3
votes
2answers
266 views

How many ways to draw the figure without lifting pencil? [duplicate]

The rules are very simple ... Star at A, end at A. From one point you can to go to the other point by only one line (no turning at cross roads). No going over any line more than once. find the ...
7
votes
3answers
304 views

What is the minimum count of steps required to complete this dominoes maze?

Here's a map: How to play Legend: (◾) = Start point ★ = Objective ⚑ = End point Mission: ...
3
votes
1answer
157 views

Sing me the song of days gone by, sing me the song that made me cry

Sing me the song of days gone by, sing me the song that made me cry. The remorse, regret, and pain I'm in, reflects the memories of what has been. Hint 1
6
votes
1answer
256 views

What's the graph relation? #2

What's the relation that joins the nodes? Open the image in a new tab if you'd like to see the diagram with better resolution. Previous What's the graph relation? #1 Hint 1
4
votes
1answer
163 views

What's the graph relation? #1

What is the relation that connects the nodes of this digraph?
3
votes
1answer
122 views

Name that node #2

What is the value of the unknown node? Previous Name that node #1 (Beginner's Level Puzzle)
5
votes
1answer
123 views

Name that node #1 (Beginner's Level Puzzle)

While Puzzling.SE has some extremely clever and difficult puzzles that are being solved by people whose intellect amazes me, I wanted to make some graph puzzles that were specifically meant for ...
2
votes
2answers
163 views

A complex matter of relations (What am I?)

There is many-a-kind of number, which sometimes makes me feel dumber. Let's say that we start from zero to four, and see if that leads us to learn some more. Some numbers you might see as a ...
1
vote
1answer
110 views

A simple matter of relations (What am I?)

Don't overthink it, just a little fun. Relations are part of graphs, of which I am one. What is my relation? Hint 1
4
votes
1answer
158 views

Which node(s) does 0 connect with in this simple graph?

If we add 0 as a node to the graph below, which node(s) will it connect to? Hint 0 Hint 1 Hint 2
0
votes
1answer
288 views

What's the number in the last node of this directed graph?

Hint 1 Hint 2 Hint 3 Background on puzzle (Spoiler Alert)
3
votes
1answer
248 views

I'm singing a song, can you follow along?

What song am I singing? I apologize for the resolution. If you open the image itself in a new tab you can magnify to get a better look at the words.
11
votes
1answer
483 views

Which node(s) does 16 connect with in this simple graph?

If we add 16 as a node to the graph below, which node(s) will it connect to? Hint 1 Hint 2 Hint 3 Hint 4 Hint 5
16
votes
1answer
1k views

What node does 11 point to?

If we included 11 in the diagram below, which node would it connect to? Hint 1
7
votes
1answer
228 views

Largest set of independent hexominoes

What is the largest set of hexominoes that can be found in which no two of them are such that one can be converted into the other by cutting out one of its component squares (thus obtaining a ...
6
votes
1answer
543 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 ...
7
votes
2answers
359 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
114 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....
20
votes
1answer
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 ...

1
2 3 4

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.