3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Surely there will not be any such graphs. If there are no vertices of degree 1, then your argument shows this. But adding a vertex of degree 1 to a graph with minimum degree 2 adds at least 1 to the number of edges of the line graph and exactly 1 to the number of edges of the graph. $\endgroup$
    – Gordon Royle
    Commented Oct 31, 2021 at 0:43
  • 1
    $\begingroup$ @GordonRoyle that is what happens when we induct forgetting the base case $\endgroup$
    – Fedor Petrov
    Commented Oct 31, 2021 at 5:45

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

Matchings: the line graph of a matching has no edges.

Paths: the line graph of every path of length $k\ge 1$ has $k-1$ edges.

Paths might be the only connected graphs with this property, which may be proved by induction as in Gordon Royle's comment.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Yes, the induction method suffices to prove that the only connected examples are paths. For disconnected graphs, you can take an arbitrary set of components and add a sufficient number of path components. So every connected graph is a component of one of these graphs. $\endgroup$
    – Brendan McKay
    Commented Oct 31, 2021 at 2:59
  • $\begingroup$ But how about this case: $G$ has one non-path component $G_0$ such that $\vert E(L(G_0)) \vert=\vert E(G_0)\vert + m$, and sufficiently many path components $G_1 \cdots G_{m+1}$. Then $\vert E(G) \vert = \vert E(L(G)) \vert+1$ since $\vert E(G_i) \vert = \vert E(L(G_i)) \vert+1$. What can we say about it? $\endgroup$
    – okw1124
    Commented Oct 31, 2021 at 10:33
  • $\begingroup$ @okw1124 That's the example I gave. $\endgroup$
    – Brendan McKay
    Commented Nov 1, 2021 at 1:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .