Return to Answer

For the case when $G$ is connected, we can argue as follows:

Since $\lvert E(G)\rvert=\lvert V(L(G))\rvert$, the inequality $\lvert E(L(G))\rvert<\lvert E(G)\rvert$ can be read as "$L(G)$ has more vertices than edges". Since $L(G)$ is connected as well, it must therefore be a tree. In particular, $L(G)$ cannot contain cycles. Therefore, $G$ cannot contain a vertex of degree 3 or higher and $G$ must be a path.

If $G$ is not connected, then every component which is a path (of length at least 1) loses one edge when transitioning to the line graph. If you have enough such components, you can make up for other components whose numbers of edges rise.

For the case when $G$ is connected, we can argue as follows:

Since $\lvert E(G)\rvert=\lvert V(L(G))\rvert$, the inequality $\lvert E(L(G))\rvert<\lvert E(G)\rvert$ can be read as "$L(G)$ has more vertices than edges". Since $L(G)$ is connected as well, it must therefore be a tree. In particular, $L(G)$ cannot contain cycles. Therefore, $G$ cannot contain a vertex of degree 3 or higher and $G$ must be a path.

If $G$ is not connected, then every component which is a path (of length at least 1) loses one edge when transitioning to the line graph. If you have enough such path components, you can make up for arbitrarily many other components whose numbers of edges rise.

For the case when $G$ is connected, we can argue as follows:

Since $\lvert E(G)\rvert=\lvert V(L(G))\rvert$, the inequality $\lvert E(L(G))\rvert<\lvert E(G)\rvert$ can be read as "$L(G)$ has more vertices than edges". Since $L(G)$ is connected as well, it must therefore be a tree. In particular, $L(G)$ cannot contain cycles. Therefore, $G$ cannot contain a vertex of degree 3 or higher and $G$ must be a path.

If $G$ is not connected, then every component which is a path (of length at least 1) loses one edge when transitioning to the line graph. If you have enough such components, you can make up for another component whose number of edges rises.

For the case when $G$ is connected, we can argue as follows:

Since $\lvert E(G)\rvert=\lvert V(L(G))\rvert$, the inequality $\lvert E(L(G))\rvert<\lvert E(G)\rvert$ can be read as "$L(G)$ has more vertices than edges". Since $L(G)$ is connected as well, it must therefore be a tree. In particular, $L(G)$ cannot contain cycles. Therefore, $G$ cannot contain a vertex of degree 3 or higher and $G$ must be a path.

If $G$ is not connected, then every component which is a path (of length at least 1) loses one edge when transitioning to the line graph. If you have enough such components, you can make up for other components whose numbers of edges rise.

For the case when $G$ is connected, we can argue as follows:

Since $|E(G)|=|V(L(G))|$, the inequality $|E(L(G))|<|E(G)|$ can be read as "$L(G)$ has more vertices than edges". Since $L(G)$ is connected as well, it must therefore be a tree. In particular, $L(G)$ cannot contain cycles. Therefore, $G$ cannot contain a vertex of degree 3 or higher and $G$ must be a path.

If $G$ is not connected, then every component which is a path (of length at least 1) looses one edge when transitioning to the line graph. If you have enough such components, you can make up for another component whose number of edges rises.

For the case when $G$ is connected, we can argue as follows:

Since $\lvert E(G)\rvert=\lvert V(L(G))\rvert$, the inequality $\lvert E(L(G))\rvert<\lvert E(G)\rvert$ can be read as "$L(G)$ has more vertices than edges". Since $L(G)$ is connected as well, it must therefore be a tree. In particular, $L(G)$ cannot contain cycles. Therefore, $G$ cannot contain a vertex of degree 3 or higher and $G$ must be a path.

If $G$ is not connected, then every component which is a path (of length at least 1) loses one edge when transitioning to the line graph. If you have enough such components, you can make up for another component whose number of edges rises.