4. A graph or a network is an object consisting of nodes (a.k.a. vertices) and links between the nodes (a.k.a edges). Graphs are an important object that is used for modelling of various practical phenomena such as road or electricity networks or a network of friends in Facebook. For the purpose of this question, we consider a graph G whose nodes corresponds to participants of a communication protocol. Two participants can directly exchange a message only if they are connected by a link. (a) Suppose that the graph G as above has n nodes and m links. Suppose that the participants want to exchange information with each other using a symmetric protocol so that every pair of participants connected by an edge hold their unique key. How many keys in total will be needed? Please provide a formula in terms of n and m an explain how you obtained it. A correct formula without any explanation will be worth 1 mark. If a formula is absent it will be zero mark even if explanation is provided. (5 marks) (b) Suppose that the graph G as above has n nodes and m links and every node is connected to at least one link Suppose that the participants want to exchange information with each other using an asymmetric protocol. How many keys in total will be needed? Please provide a formula in terms of n and m an explain how you obtained it. A correct formula without any explanation will be worth 1 mark. If a formula is absent it will be zero mark even if explanation is provided. (5 marks) Answer. Every user will have somebody to communicate with (because every user is connected to a link). Each user has exactly two keys, one public and one private. So, the total number of keys is 2n. (c) Suppose that the graph G is a clique of n nodes (that is, each pair of nodes is connected by a link). Suppose that the participants want to exchange information with each other using a symmetric protocol so that every pair of participants connected by an edge hold their unique key. How many keys in total will be needed? Please provide a formula in terms of n and explain how you obtained it. A correct formula without any explanation will be worth 1 mark. If a formula is absent it will be zero mark even if explanation is provided. (5 marks) Answer. This is a special case of part a), so the number of keys is as the number of edges in a clique of n nodes which is nn-1)/2. (d) Suppose that the graph G has n nodes such that n is even. The vertices of G are divided into two equal size subsets Vi and V of size n/2 each. Each element of V, is connected by edge to each element of V2. There are no edges between two elements of V, nor between two elements of V2. Suppose that the participants want to exchange information with each other using a symmetric protocol so that every pair of participants connected by an edge hold their unique key. How many keys in total will be needed? Please provide a formula in terms of n and explain how you obtained it. A correct formula without any explanation will be worth 1 mark. If a formula is absent it will be zero mark even if explanation is provided. (5 marks) Answer. Again, this is a special case for part a), so the number of keys equals the number of edges in the specified graph which is n/2*n/2 = n2/4
