The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
2
votes
3answers
361 views

Find the least number of Dragons required

The following graph represents the positions at Castle Dragonstone. Each edge indicates that the positions are within sight of each other. This is not transitive; i.e., you can't see all the way along ...
2
votes
2answers
168 views

Find a tour through the exhibition [duplicate]

Is there a way to take a tour through the exhibition that passes through each door exactly once? Source: chegg.com
18
votes
1answer
407 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 ...
8
votes
1answer
424 views

A perfect metro map

You are working for a company and asked to create a perfect metro map where there will be as many stops as possible. But there are two constraints which limits the number of tracks (railroads) and ...
11
votes
5answers
759 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 ...
20
votes
2answers
766 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 ...
6
votes
2answers
145 views

A problem about oriented face in Square grid

Consider a $n \times n$ square grid (finite) (a square is divided into smaller squares by lines parallel to its sides). The boundary of the square is oriented, (clockwise or anticlockwise) that is, a ...
4
votes
2answers
201 views

Four mutually adjacent US states (not the Four Corners) [closed]

The question Is there a proof that a map of the United States requires 4 colors? was answered by showing that Nevada has five neighbors, each adjacent to the next (an "odd wheel"). "Adjacent" here ...
21
votes
2answers
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 ...
16
votes
5answers
773 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 ...
9
votes
4answers
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. ...
2
votes
4answers
229 views

Create a special Playing Schedule - Logical/Mathematical Solution

Last Week in Training (I'm a Cycleball player) a logial problem/puzzle tricked us. And I'm wondering if there exists a logical solution for the next time. Cycleball is played in pairs (2 Players vs. ...
8
votes
2answers
806 views

Eight queens on the chessboard with mirrors

A 8-by-8 chessboard has two mirrors added on its left and right margin. The mirrors reflect the queen moves so that a queen threatens additional squares on the board. A queen threatens all squares in ...
5
votes
3answers
409 views

Crossing Frog Lake

Our Red Frog wants to get to the Orange Frog, but he can only jump right and down, but over multiple lilies if he chooses, although he can't stay still. How many ways can he do it?
14
votes
5answers
523 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 ...
6
votes
3answers
276 views

Professor Halfbrain and the tennis club

The other day, I met with professor Halfbrain and professor Erasmus in the coffee house. Professor Erasmus told us that he had been working on a schedule for a tennis club with $30$ senior and $30$ ...
41
votes
1answer
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. ...
16
votes
2answers
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 ...
14
votes
4answers
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 ...
26
votes
3answers
823 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, ..., ...
3
votes
1answer
488 views

The Unknown Prison of Unknown Size

Inspired by The Circular Prison of Unknown Size by @MikeEarnest (Great puzzle, by the way!) The rules are almost same, so I won't waste time by rewriting them all here. (They're still valid, though.) ...
10
votes
2answers
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 ...
8
votes
1answer
523 views

Lost In Boston: How do I Get Home?

I'm posting this from my phone again because I've gotten hopelessly lost in Boston, really want to go home, and desperately need the help of some clever people on the internet. Please help me - I'm ...
14
votes
1answer
988 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. ...
6
votes
3answers
1k views

A party puzzler

At a party, everybody is friend with exactly $22$ of the other persons present. Whenever two persons are friends, they do not have any friends in common. Whenever two persons are not friends, they ...
9
votes
6answers
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 ...
15
votes
3answers
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 ...
10
votes
2answers
520 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-...
12
votes
5answers
424 views

Twitter Followers

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: ...
1
vote
3answers
303 views

Computer-controlled maze

You have to build a maze whose exit can be changed by a computer. The maze consists of one entrance, hallways which can intersect, and $n$ exits. The computer has several wires leaving it each ...
13
votes
1answer
787 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?
2
votes
2answers
948 views

Is there any solution for this puzzle? [duplicate]

There is a house with 5 room and one door with every single wall as shown in following figure. You have to visit every door exactly once but there is a condition that you cannot cross the path. I ...
35
votes
11answers
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 ...
18
votes
6answers
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 ...
12
votes
4answers
938 views

The Duplicator and the Safe

...
7
votes
1answer
394 views

The Robostanchion Exam (a puzzle about game-graph connectedness)

The St. Čapek Crowd Control Academy, June, 2115. Commander Gall is worried. On one hand, the graduating class this year is the most promising in the institution's history, every cadet's reasoning ...
9
votes
1answer
600 views

Building a cheap road

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 ...
7
votes
3answers
897 views

Spreading Gossip

Initially, each of 50 Puzzling Stack Exchange users have a single distinct juicy bit of gossip not known to the others. If $A$ sends an email to $B$, that email can include all the bits of gossip $...
8
votes
2answers
378 views

Bracing a Flexible Grid

Suppose that you build an $n$ by $n$ grid out of metal rods, joined at their ends in such a way that they can rotate about the joints. Below is the grid when $n=3$, along with an illustration of its ...
10
votes
5answers
815 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 ...
16
votes
4answers
12k 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 ...
-6
votes
2answers
385 views

Checkerboard piece inverting game

Marco and Leonardo decided to play a game on a checkerbard of 4×4 squares. The board is initially filled with two-sided identical coins. The game notes that these two players play turns alternatively ...
7
votes
1answer
628 views

Smallest number of matchsticks for a 3D structure with 6 matchsticks at each vertex

Make an as small as possible three dimensional structure of matchsticks, all of which have equal length, such that the end of each matchstick meets exactly five other ends. A matchstick is not allowed ...
4
votes
2answers
741 views

Puzzle pieces, each in contact with 5 others

You are asked to create puzzle pieces by joining together identical squares. This needs to be done such that the puzzle pieces can be arranged in a pattern with each piece being in contact with ...
14
votes
3answers
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 ...
10
votes
2answers
849 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 ...
9
votes
1answer
414 views

Generalisation of tours on chessboards

It's well-known that a knight placed on one square of a chessboard can get to any other square, but a bishop can only reach half the squares from a fixed starting point. Another question on this site ...
4
votes
3answers
392 views

Every tournament has a dominant player

A tournament was played round-robin: each pair of players played a match where one defeated the other. Prove that there was a player for which every other player either lost to them or lost to someone ...
10
votes
6answers
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. ...
9
votes
1answer
322 views

What factors affect the difficulty of Hamiltonian puzzles?

There is a type of puzzle which can be modelled as finding a Hamiltonian path through a graph. One example is the Icosian game. What factors affect the difficulty of such puzzles, to be solved by ...