An important object containing information about a weighted graph G(V,E,w) is its Laplacian matrix. Given a numbering of the vertices of the graph, it's an n by n square matrix LG, where n is the number of vertices in the graph, with the entries:
where vk → vl means that there is a directed edge from vertex vk to the vertex vl, and where w is the weight function.
Exercise (*). Given a directed graph G without cycles, prove that one can number its vertices so that the corresponding Laplacian matrix LG is triangular.
Given a weighted graph with boundary it is often convenient to number its boundary vertices first and to write its Laplacian matrix in the block form.
Exercise (*). Prove that a function/vector u is harmonic at the interior nodes of a graph G if
be a block matrix with an invertible square block D.
Then the Schur complement of the matrix M w/respect of the block D is the matrix
The Leibniz definition of determinant (a multilinear function in the rows and columns) of a square n by n matrix M is:
Exercise (*). Prove the following determinant identity for a square matrix M:
The following matrix W(G) consisting of random walk exiting probabilities (sums over weighted paths in a graph) plays an important role as boundary measurement for inverse problems. Suppose a weighted graph G has N boundary nodes, then the kl 'th entry of the N by N matrix equals to the probability that the first boundary vertex, that a particle starting its random walk at the boundary vertex vk occupies, is the boundary vertex vl. For a finite connected graph the columns of the matrix W(G) add up to 1.
Exercise (**). Derive an explicit formula for the matrix W(G) in terms of the blocks of Laplace matrix L(G) of the graph G.
Exercise (***). Prove the following expansion formulas for entries and blocks of the matrix W(G),
- for two boundary vertices pk and pl of a graph G
- for two distinct boundary vertices vk and vl of a graph G
- for two disjoint subsets of boundary vertices P and Q of size n of a graph G, see , and 
The exercises above provide a bridge b/w connectivity property of graph G and ranks of submatrices of its Laplacian matrix L(G) and the matrix of hitting probabilities W(G).
Exercise (*). Let G be a planar graph w/natural boundary, numbered circulary. Let P and Q be two non-interlacing subsets of boundary nodes of size n. Prove that
w/the strict inequality iff there is a disjoint set of paths from P to Q.
Exercise (*). Show that the numbers of paths in the following graph are equal to the binomial coefficients.
Gluing the graphs w/out loops corresponds to multiplication of the weighted paths matrices.
Exercise (**). Use the result of the previous exercise to it to prove the following Pascal triangle identity, see,
Exercise (***). Give a proof of a Menger's theorem based on the results of the exercise above: Let G be a finite graph and p and q two vertices that are not neighbors. Then the size of the minimum vertex cut for p and q (the minimum number of vertices whose removal disconnects p and q) is equal to the maximum number of pairwise vertex-independent paths from p to q.