Determine a formula for the number of triangles in the line graph $L(G)$ in term of quantities in $G$

Question

Determine a formula for the number of triangles in the line graph $L(G)$ in term of quantities in $G$

I know that the line graph $L(G)$ of $G$ is a graph whose vertices are one to one correspondence to the edges in $G$ such that 2 vertices of $L(G)$ adjacent iff the corressponding eges in $G$ adjacent.

So let $a,b,c$ be vertices in $L(G)$ then we have the triangle $a,b,c,a$ if the edges $a,b,c$ is on $K_3$ or$K_{1,3}$.

How can I use this to find the formula for the number of triangles in the line graph $L(G)$ in term of quantities in $G$

Answer 1

If the incidence matrix of a graph $G$ is known (denote it by C, which is a $m\times n$-matrix),

then the adjacency matrix of the line graph $L(G)$ is $L=C^TC-2I_n$.

Then, $\frac{trace(L^3)}{6}$ is the number of triangles in $L(G)$.

Answer 2

Each triangle in the line graph $L(G)$ corresponds to either a triangle in $G$ or a set of three edges in $G$ that are incident to a common vertex. The number of sets of three edges in $G$ that are incident to a vertex of degree $i$ is ${d_i \choose 3}$, where $d_i$ is the degree of the $i$th vertex of $G$. So the number of triangles in $L(G)$ is equal to the sum of the number of triangles in $G$ and the quantity $\sum_i {d_i \choose 3}$.

Given a graph $H$, let $A$ be its adjacency matrix. The number of walks of length $\ell$ in $H$ from the $i$th to the $j$th vertex of $H$ is $A^\ell(i,j)$. The number of closed walks of length $\ell$ in $H$ is $\sum_i A^\ell(i,i)$, which equals the trace of $A^\ell$ (or the sum of the $\ell$th powers of the eigenvalues of $A$). Each triangle in a graph can be traversed starting from any one of the three vertices and going in any one of two directions, whence the number of closed-walks of length 3 on each triangle of a graph is 6. Hence, the number of triangles in $H$ is $trace(A^3)/6$. This formula specifies the number of triangles in a graph in terms of its adjacency matrix. There is a formula for the adjacency matrix $A_{L(G)}$ of $L(G)$ in terms of the incidence matrix of $G$: if $G$ has $n$ vertices and $m$ edges and its incidence matrix is the $n \times m$ matrix $X$, then $X^T X = A_{L(G)}+ 2I_m$