Difference between revisions of "One-way roads"

From Math Puzzle Wiki
Jump to: navigation, search
(Puzzle)
(Puzzle)
 
Line 3: Line 3:
 
==Puzzle==
 
==Puzzle==
  
A county has <math>n > 4</math> cities. Is it possible to connect some pairs of cities by one-way roads so that one can travel from every city to every other city using only one or two roads?  If so, how?  Note that for every pair of cities A and B, only one road connecting A with B is allowed; this road leads from A to B or from B to A, but not both ways.
+
A county has <m>n > 4</m> cities. Is it possible to connect some pairs of cities by one-way roads so that one can travel from every city to every other city using only one or two roads?  If so, how?  Note that for every pair of cities A and B, only one road connecting A with B is allowed; this road leads from A to B or from B to A, but not both ways.
  
 
[[Category: Graph theory]]
 
[[Category: Graph theory]]
 
[[Category: New]]
 
[[Category: New]]
 
[[Category: Needs solution]]
 
[[Category: Needs solution]]

Current revision as of 20:11, 24 July 2017

Found this one on the SUNY Stony Brook Math Problem of the Month archives.

Puzzle

A county has <m>n > 4</m> cities. Is it possible to connect some pairs of cities by one-way roads so that one can travel from every city to every other city using only one or two roads? If so, how? Note that for every pair of cities A and B, only one road connecting A with B is allowed; this road leads from A to B or from B to A, but not both ways.