CMI2011-B-01b

Question

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.

Two roads are said to be $\text{adjacent}$ to each other if they serve a common building. A set of roads is said to be $\text{preferred}$ if:

• No two roads in the set are adjacent, and,
• Each building is served by at least one road in the set.

1. Is it always possible to find a preferred set of roads?
2. Is it ever possible to find two sets of preferred roads differing in at least one road?

Substantiate your answers by either proving the assertion or providing a counterexample.

Answer 1

 

consider A,B,C....as buildings 1,2,3.... as roads

1)  set {1,3,6}  it not prefrred set...but it is possible to find prefffred set..for some other graph..(remove D,G building with roads 4,7 then u will find  prefffred set {1,3,6} )

2) it is not possible  at all...try in graph

so both statements are wrong

Answer 2

We can consider this problem in terms of graph. Based on the given conditions the roads and buildings form a tree.

(i) No. This is not always possible. Consider the following tree. We can chose either $A-B$ or $B-C$ but both will cause a vertex (building in question) to be disconnected. 

 

(ii) No. Suppose we have two edge sets which differs by exactly one edge say $e_1$ and $e_2.$ Both $e_1$ and $e_2$ must be connecting two vertices not connected by any other edges. This means they must be connecting the same vertices in the two sets and since we have a tree, $e_1 = e_2.$ 
Now suppose $2$ edges differ. Then we have $4$ vertices which needs to be connected by these $2.$ Let $e_1$ connect $v_1$ and $v_2$ and $e_2$ connect $v_3$ and $v_4.$ Now we can choose edges $e_1'$ which connects $v_1$ and $v_3$ and $e_2'$ which connects $v_2$ and $v_4.$ But those $2$ edges are not possible together as this would make $v_1 - v_2 - v_4 -v _3$ a cycle which is not possible in a tree. So, the only way to choose $2$ edges are $e_1$ and $e_2$ only. 

Similarly we can prove for $3$ edges and more.