Problem 2. (25 pts) A random graph G(n, p) is generated using the following algorithm. First, we fix n nodes which we denote as v, 2, ..., Vn- Then, for every two nodes (v, vj) we toss an independent coin that comes out 'heads' with probability -pand we put no edge between v and vj. In other words, for every pair of nodes vi,vj we put a (non-directed) edge between them with probability p and this is done independently for each possible pair of nodes (a) (10 pts) What is the expected number of edges in a random graph G(n,p)? f the coin comes up 'heads' we draw the edge fvi,vjl; o/w (b) (15 pts) What is the expected number of triangles in a random graph G(n, p)? A triangle: a triplet of distinct nodes [vi, vj, vk\ such that all 3 edges (fvi,vjl. Ivj, vkI, svi, v*\) are present in the graph For example, if n -5, pand we happened to pick the graph shown in Figure 2, then we have a graph with 7 edges and 2 triangles ( ,v4 ,V5} and {U2U3,U4) U3 U5 Figure 2 For example, if n 3 and pthen all possible graphs over) 3 edges that G(3, ) might generate are given in Figure 3 along their corresponding probabilities. Thus 6) E/#triangles]-0 x +3 27 Figure 3 Problem 2. (25 pts) A random graph G(n, p) is generated using the following algorithm. First, we fix n nodes which we denote as v, 2, ..., Vn- Then, for every two nodes (v, vj) we toss an independent coin that comes out 'heads' with probability -pand we put no edge between v and vj. In other words, for every pair of nodes vi,vj we put a (non-directed) edge between them with probability p and this is done independently for each possible pair of nodes (a) (10 pts) What is the expected number of edges in a random graph G(n,p)? f the coin comes up 'heads' we draw the edge fvi,vjl; o/w (b) (15 pts) What is the expected number of triangles in a random graph G(n, p)? A triangle: a triplet of distinct nodes [vi, vj, vk\ such that all 3 edges (fvi,vjl. Ivj, vkI, svi, v*\) are present in the graph For example, if n -5, pand we happened to pick the graph shown in Figure 2, then we have a graph with 7 edges and 2 triangles ( ,v4 ,V5} and {U2U3,U4) U3 U5 Figure 2 For example, if n 3 and pthen all possible graphs over) 3 edges that G(3, ) might generate are given in Figure 3 along their corresponding probabilities. Thus 6) E/#triangles]-0 x +3 27 Figure 3