Elementary properties of the graph Laplacian

In this minihomework, we will prove some of the basic properties of the graph Laplacian. First,
recall from the notes that
Definition. The boundary map for a graph G is the v × e matrix defined by
∂(ei) = head(ei) − tail(ei)
The graph Laplacian LG for a graph G is the symmetric v × v matrix defined by
LG := ∂∂T
.
We proved in the notes that for any vector v ∈ R
v
, we have
QLG
(v) = hv, LG vi =
Xe
i=1

vhead(ei) − vtail(ei)

2
.

1. (10 points) Suppose that G and G0 have the same vertices and edges v1, . . . , vv = v
   0
   1
   , . . . , v0
   v0
   and e1, . . . , ee = e
   0
   1
   , . . . , e0
   e
   0, but the orientations of the edges may not agree.
   Prove that LG = LG0.

Sample Solution