677 views
1 votes
1 votes

A multinational company is developing an industrial area with many buildings. They want to connect the buildings with a set of roads so that:

  • Each road connects exactly two buildings.
  • Any two buildings are connected via a sequence of roads.
  • Omitting any road leads to at least two buildings not being connected by any sequence of roads.

Is it always possible to colour each building with either red or blue so that every road connects a red and blue building?

2 Answers

1 votes
1 votes
we get a tree as the resulting data structure from the 3 rules given.the chromatic number of a tree is 2.

Related questions