Skip to main content
2 of 2
TeX
LSpice
  • 12.9k
  • 4
  • 45
  • 69

What kind of graph has more edges than its line graph?

The definition of a line graph is as follows:

Given a graph $G$, its line graph $L(G)$ is a graph such that

  1. each vertex of $L(G)$ represents an edge of $G$.
  2. 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?

okw1124
  • 341
  • 1
  • 9