Question

We are deploying cryptographic schemes on the n computers of a network (each com- puter has exactly one cryptographic scheme deployed on t), and a total of m different cryptographic schemes are deployed on the network. Further in order to be secure, we re- quire two directly connected computers to employ different cryptographic schemes. Let k be the largest number of computers in the network such that no two of them are connected directly to each other. Show that m 2 n/k.

Answer 1

Lets us divide the computers in groups so that in each group no two computers are connected but there is at least one connection from one group to another group of computers. Since there is a connection from one group to another group of computers, so different cryptographic scheme has to be deployed in each group. But no two computer are connected in a group, so a single cryptographic scheme can be deployed on all computers in a group.

Then size of each group is less than or equal to as given in question.

Since there are total computers, so number of groups is greater than or equal to $\frac{n}{k}$.

Hence number of cryptographic schemes deployed should be greater than or equal to $\frac{n}{k}$

i. e.          

7L m 2