Find a connected graph $G$ which is isomorphic to its line graph. Find a connected graph $G$ with $n, (n \ge 3 )$ nodes with the property:
$$G \cong L(G)$$
My try:
The complete graph with 3 nodes ($K_3$) seems like a good candidate for this problem but I don't know how to prove it formally.
 A: Suppose $G$ is a (finite simple) graph satisfying the condition $L(G)\cong G.$ Suppose $G$ has $n$ vertices, and let's try to figure out what its degree sequence $d_1,d_2,\dots,d_n$ can be.
Since $L(L(G))\cong L(G)\cong G,$ the three graphs $G,L(G),L(L(G))$ all have the same number of vertices, i.e., both $G$ and $L(G)$ have $n$ edges.
The number of edges in $G$ is $\frac12\sum_{i=1}^nd_1,$ and the number of edges in $L(G)$ is $\sum_{i=1}^n\binom{d_i}2,$ so we have
$$n=\frac12\sum_{i=1}^nd_i=\sum_{i=1}^n\binom{d_i}2.$$
It follows from these equations that
$$\sum_{i=1}^n(d_i-2)^2=0,$$
i.e.,
$$d_1=d_2=\cdots=d_n=2.$$
To see this, instead of doing the algebra directly, let's recast it in terms of probability. Let the random variable $X$ be the degree of a randomly chosen vertex of $G.$ Then the average degree of $G$ is
$$\mu=E[X]=\frac1n\sum_{i=1}^nd_i=2,$$
and
$$E\left[\binom X2\right]=\frac1n\sum_{i=1}^n\binom{d_i}2=1,$$
i.e.,
$$1=E\left[\binom X2\right]=E\left[\frac{X^2-X}2\right]=\frac12E\left[X^2\right]-\frac12E[X],$$
so
$$E\left[X^2\right]=E[X]+2=4=\mu^2$$
and
$$\text{Var}(X)=E\left[(X-\mu)^2\right]=E\left[X^2\right]-\mu^2=0.$$
We have shown that a graph which is isomorphic to its line graph must be $2$-regular; conversely, a
$2$-regular graph is a sum of cycles, which is clearly isomorphic to its line graph. Thus, the solutions of $L(G)\cong G$ are just the $2$-regular graphs, and the connected solutions are just the cycles.
A: For any $n\geq3$ consider the cycle graph $C_n$. If you want to build a specific bijection between $C_n$ and $\operatorname{L}(C_n)$, then just temporarily impose a direction on the edges in $C_n$ such that each vertex has out-degree one (all edges point the same way), and have each vertex of $C_n$ map to the vertex of $\operatorname{L}(C_n)$ that corresponds to edge leaving it. Explaining why this is an isomorphism is tedious, but not difficult.
