In this problem, we will compare and contrast adjacency matrices and Laplacian matrices, both of which are induced from graph representations. Throughout the problem we consider (and your answers should provide) only undirected graphs without loops. Given a graph G = (V, E).V = {1, ..., n}. E subsetof V times V. an adjacency matrix A elementof {0, l}^n times n is defined by A_ij = 1 if (i, j) elementof E and A_ij = 0 if (i, j) notelement E, a Laplacian matrix L elementof z^n times n is defined as L = D - A where A is the adjancency matrix and D is a diagonal matrix where D_ii is the degree of node i. Part 1 Draw a 3-node connected graph whose adjacency matrix is full-rank Draw a 3-node connected graph whose adjacency matrix is rank deficient Provide the adjancency matrices of both graphs. Part 2 Generalize the rank-deficient graph in part 1 to an n-node graph with n - 1 edges whose adjacency matrix has rank 2 Provide a general definition of the adjacency matrix of such a graph. Part 3 Consider the Laplacian matrix of an arbitrary connected graph G Show that any such Laplacian matrix is rank-deficient, in particular find v element R^n such that Lv=0. Part 4 Consider the Laplacian matrix of an arbitrary connected graph G Show that any such Laplacian matrix has rank n - 1. To do this, consider any w element R^n such that Lw = 0 and rank ([v w]) = 2. where v is your solution to Part 3. Arrive at a contradiction by showing that Az notequalsto 0. where z = (w - alphav) and alpha is picked to annihilate the largest entry in w