in Combinatory
572 views
0 votes
0 votes

A computer net network consists of 6 computers.Each computer is directly connected to 0 or more computers.Based on pegion hole principle which one of the following is true?

1) There is atleast 5 computer in the network that is directly connected to same no of other computers

2) There is atleast 4 computer in the network that is directly connected to same no of other computers

3) There is atleast 3 computer in the network that is directly connected to same no of other computers

4) There is atleast 2 computer in the network that is directly connected to same no of other computers

in Combinatory
by
572 views

1 Answer

0 votes
0 votes
Best answer

Correct answer should be Option D.

It would be better to view this computer network as a simple undirected graph of 6 vertices, where degree of each vertex is greater than or equal to zero.

In this graph we have to find out at least how many vertices must have same degree.

Degree of a vertex can be any one element from the set D = {0, 1, 2, 3, 4, 5} (since number of vertices are 6 in the graph & the graph is simple so multiple edges & self loops are not allowed & thus each vertex can have a maximum of 5 degree).

Now if we are assigning a DISTINCT DEGREE to each of the 6 vertices then, we have to assign a distict element of D to each of the nodes & 0, 1, 2, 3, 4, 5 will be assigned to six nodes.

But we know that sum of degree of all the vertices of a graph must be an even number.

& here it can be observed that 0 + 1 + 2 + 3 + 4 + 5 = 15 which is of course odd.

So it is clear that we can’t assign a different degree to each of the vertices.

Also it can be observed that this ODD DEGREE PROBLEM can be solved by replacing any of assigned odd degree {1, 3, 5} with any of the even degrees {0, 2, 4} then this problem can be solved, & such a graph will be a valid graph.

For example choose degrees (0, 1, 2, 3, 4, 4) or (0, 1, 2, 2, 4, 5) or (0, 0, 2, 3, 4, 5) and so on, sum of degrees in all this case will be even.

Thus we have tried our best to assign as much distinct degree as possible to the six vertices along with keeping the graph valid, & found that at least 2 of the vertices MUST have a common degree.

So the correct option would be option D.

Moreover we can also guarantee that the repeating degree must even, it can’t be odd.