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.

103 questions
Filter by
Sorted by
Tagged with
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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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. ...
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 ...
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?
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 ...
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$ ...
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. ...
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 ...
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 ...
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, ..., ...
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.) ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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-...
424 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: ...
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 ...
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?
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 ...
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 ...
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 ...
938 views

...
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 ...
600 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 ...
897 views

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