Simple case & intuitive explanation
The elements of the (simple -- i.e., weights $0$ or $1$) graph Laplacian are given by (from Wikipedia):
$$
L_{ij}:=
\begin{cases}
\deg(v_i),& \text{if } i=j;\\
-1, & \text{if }i\sim j\textrm{ (is connected);}\\
0, & \text{otherwise.}
\end{cases}
$$
So an example graph Laplacian might look like:
$$
L_{\text{example}}=\begin{bmatrix}
2&-1&-1&0 \\
-1&3&-1&-1\\
-1&-1&2&0\\
0&-1&0&1
\end{bmatrix}
$$
Notice how each row sums to zero because the diagonal element is the number of connected vertices and the off-diagonal elements subtract $1$ for every connected vertex. The exact same reason is why each column sums to zero (i.e., the matrix is symmetric).
Now let $x\in \{-1,1\}^n$, where $x_i$ represents whether vertex $i$ is on one side of the cut or the other. One example could be:
$$
x_{\text{example}}=\begin{bmatrix}
1\\
-1\\
-1\\
1
\end{bmatrix}
$$
so computing $L_{\text{example}}x_{\text{example}}$ would return a column vector. Each $i$th element in this column vector would be calculated by taking the degree of vertex $i$, adding $1$ for each connected vertex on the other side of the cut, and subtracting $1$ for each connected vertex on the same side of the cut, then arbitrarily multiplying by $-1$ if it’s on a specific side of the cut. This arbitrary multiplication doesn’t matter though, because the purpose of computing $x_{\text{example}}^TL_{\text{example}}x_{\text{example}}$ is to cancel out these minus signs. For the example above,
$$
x_{\text{example}}^TL_{\text{example}}x_{\text{example}}=
\begin{bmatrix}
1&
-1&
-1&
1
\end{bmatrix}
\begin{bmatrix}
4\\
-4\\
-2\\
2
\end{bmatrix}
=12
$$
Thus, it’s easy to see that element $i$ in $Lx$ gives (up to $-1$): $$
(Lx)_i=
\deg(v_i)+\Bigg(\sum_{
\substack{j\sim i,\\
j\text{ other side}}
}1\Bigg)
-\Bigg(\sum_{\substack{j\sim i,\\
j\text{ same side}}
}1\Bigg)$$
We also see that $x^TLx$ gives the sum of these:
$$
\begin{align}
x^TLx&=\sum_{i\in V}\deg(v_i)+2(\text{# edges crossing cut})-2(\text{# edges not crossing cut})\\
&=2(\text{# edges}+\text{# edges crossing cut}-\text{# edges not crossing cut})\\
&=4(\text{# edges crossing cut})
\end{align}$$
because
$$
\text{# edges}=\text{# edges crossing cut}+\text{# edges not crossing cut}.
$$
Thus, this representation with $L$ (specifically $x^TLx$) is useful in convex optimization/max cut because it is optimizing something proportional to the number of edges crossing the cut.
Clearly this is the result for an unweighted graph Laplacian. The generalization to a graph with weighted edges is simple and left as an exercise for the reader.
General graph Laplacian with weights in $\mathbb{R}_+$
I omit the lengthy explanation, as that is very similar to the above. Here is the math:
$$
L_{G_{ij}}:=
\begin{cases}
\sum_{k\in V}w_{ik}, & \text{if } i=j;\\
-w_{ij}, & \text{if }i\neq j;
\end{cases}
$$
where we take $w_{ij}=0$ if $i,j$ are not connected. We also define $w_{ii}=0$ because no edges exist from one node to itself.
\begin{align}
\implies
\left\lvert\big[L_Gx\big]_i\right\rvert
&=
\sum_{k\in V}w_{ik}
-\sum_{\substack{k\in V,\\ \text{same side}}}w_{ik}
+\sum_{\substack{k\in V,\\ \text{other side}}}w_{ik}
\\ &=
2\sum_{\substack{k\in V,\\ \text{other side}}}w_{ik}
\\
\implies
x^TL_Gx
&=
2\sum_{i\in V}\sum_{\substack{k\in V,\\ \text{other side}}}w_{ik}
\\ &=
2\sum_{i\in V}\sum_{j\in V}w_{ij}(x_i-x_j)^2/4
\\ &=
\dfrac{1}{2}\sum_{i,j\in V}w_{ij}(x_i-x_j)^2
\end{align}
This answers the original question in full.
