Finding the inverse of line graphs L(G)

Question

I just learned about line graphs $L(G)$ such that all vertices $v$ in $L(G)$ represent edges in $G$.

Is there a way to find for any graph $G$, a graph $G'$ such that $G = L(G')$?

The potential usage of this would be that you could find G' and test it for Eulerianism and then therefore have a algorithm for Hamiltonian cycles. Because of that I assume this must not be possible. If so I would be interested in why it isn't possible?

Answer 1

The simple reason is that not every graph is a line graph, so this inverse won't always exist. For example, the star graph with $4$ vertices (that is, the graph with vertex set $u,v_1,v_2,v_3$ and edges $uv_1,uv_2,uv_3$) is not a line graph.

To see this, suppose that it is the line graph of some other graph $G'$, and use $a,b,c,\ldots$ for vertices of $G'$. $u$ must represent some edge $ab$ say. Then $v_1$ is adjacent to $u$ in the line graph, so represents an edge with a common vertex, say $bc$.

Now $v_2$ has to represent an edge with a vertex in common with $ab$ but not with $bc$. So it represents an edge of the form $ad$. But $v_3$ now has to represent an edge with a vertex in common with $ab$ but not with either $bc$ or $ad$, which is impossible.

Answer 2

Doug West's Introduction to Graph Theory (2nd Edition), section 7.1, gives several characterizations of line graphs. There is a characterization involving cliques:

$G = L(H) \iff$ $G$ can be decomposed into cliques with each vertex of $G$ appearing in at most two cliques.

Another characterization gives a list of $9$ forbidden induced subgraphs, one of which is $K_{1,3}$ as demonstrated in Especially Lime's answer.

If you don't have access to West's text, you can take a look at the Characterization section of the Wikipedia entry.