Return to Revisions

If $|E(L(G))|<|E(G)|$, then the same holds for at least one component of $G$, and so we can assume that $G$ is connected. Then $L(G)$ is connected as well. Since $|E(G)|=|V(L(G))|$, the inequality $|E(L(G))|<|E(G)|$ can be read as "$L(G)$ has more vertices than edges". It is well-known that such a graph must be a tree. In particular, $L(G)$ cannot contain cycles. Therefore, $G$ cannot contain a vertex of degree 3 and $G$ must be a union of cycles and at least one path.