The definition of a line graph is as follows:
Given a graph $G$, its line graph $L(G)$ is a graph such that
- each vertex of $L(G)$ represents an edge of $G$.
- two vertices of $L(G)$ are adjacent if and only if their corresponding edges share a common endpoint ("are incident") in $G$.
I am curious about what kind of graph satisfies $\lvert E(L(G))\rvert < \lvert E(G) \rvert$.
It is a well-known fact that $$\lvert E(L(G)) \rvert=\sum_{i=1}^n {d_i \choose 2}$$ where the degree sequence of $G$ is $d_1,\dotsc,d_n$.
Now I have $$\lvert E(L(G))\rvert – \lvert E(G) \rvert<0 \Leftrightarrow \sum_{i=1}^n d_i(d_i-2) < 0.$$
Obviously, isolated vertices and cycles can be ignored since $d_i(d_i-2)=0$.
So remaining cases are $d_i=1$ or $d_i \geq 3$.
I observed that if $d_j \geq 3$ then $$d_j < \sqrt{n}+1.$$
Otherwise $d_j(d_j-2) \geq n-1$ so that $$\sum_{i=1}^n d_i(d_i-2) \geq d_j(d_j-2)+(-1)\cdot(n-1) \geq 0.$$
So I considered the union of stars with the degree of ‘center’ less than $\sqrt{n}+1$, but it didn't work well.
I have no idea how to proceed from here to find the properties of $G$.
Would you give me advice?
Best 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 path components, you can make up for arbitrarily many other components whose numbers of edges rise.