The only finite connected graphs $G$ that are isomorphic to their line graph $L(G)$ are the cycle graphs $C_n$ (see this link for example).

There are connected countable graphs that are isomorphic to their line graph:

  • $G=(\omega,E)$ where $E=\{\{k,k+1\}: k\in\omega\}$;
  • $G=(\mathbb{Z},E)$ where $E=\{\{k,k+1\}: k\in\mathbb{Z}\}$.

Note that in the second graph, all vertices have degree 2, which makes it into a kind of "infinite cycle". (An interesting side question would be whether these are the only connected countable graphs (up to isomorphism) that are isomorphic to their line graph.)

Question. Is there a connected graph $G=(V,E)$ with $V$ uncountable such that $G\cong L(G)$?

  • $\begingroup$ That's right - > just edited $\endgroup$ – Dominic van der Zypen Jan 23 '15 at 9:10
  • $\begingroup$ Regarding the side question, the complete graph with a countable number of vertices is isomorphic to its line graph. $\endgroup$ – Timothy Chow Jan 23 '15 at 19:59
  • $\begingroup$ I'm wondering if maybe your real question is about graphs of bounded degree? $\endgroup$ – Timothy Chow Jan 23 '15 at 20:10
  • 3
    $\begingroup$ @TimothyChow: It is not hard to see that if $G\cong L(G)$ and $G$ has a vertex of degree at least 3, then $G$ has a vertex of degree at least $n$ for all $n\in\mathbb{N}$. Basically, start with a graph with a vertex of degree 3 and one more connected edge and then iterate the operation $L$; all the graphs obtained from this must embed in $G$, but they have vertices of arbitrarily high degree. $\endgroup$ – Eric Wofsey Jan 24 '15 at 2:34

Note first that $L$ is naturally an endofunctor on the category of graphs and injective graph-homomorphisms that commutes with filtered colimits. Let $G$ be any graph such that there is an embedding $i:G\to L(G)$. This gives rise to an embedding $L(i):L(G)\to L(L(G))$, an embedding $L(L(i)):L(L(G))\to L(L(L(G)))$, and so on. Let $L^\omega(G)$ be the colimit of $G\to L(G)\to L(L(G))\to \dots$. Since $L$ commutes with filtered colimits, there are canonical isomorphisms $$L(L^\omega(G))\cong L(\varinjlim(G\to L(G)\to\dots))\cong \varinjlim( L(G)\to L(L(G))\to\dots)\cong L^\omega(G).$$

Furthermore, if $G$ is connected, so is $L^\omega(G)$, and if $G$ is infinite, $L^\omega(G)$ has the same cardinality as $G$. Thus to get a connected graph of a given infinite cardinality isomorphic to its line graph, it suffices to give a connected graph $G$ of that cardinality that embeds in $L(G)$. But this is easy; for instance, complete graphs work. In fact, any connected graph whose cardinality $\kappa$ has uncountable cofinality works, since such a graph must contain a vertex of degree $\kappa$, and thus $L(G)$ contains a clique of size $\kappa$.

  • 2
    $\begingroup$ A connected graph of cardinality $\aleph_\omega$ does not necessarily have a vertex of degree $\aleph_\omega$. $\endgroup$ – bof Jan 23 '15 at 9:35
  • $\begingroup$ bof: Thanks, corrected. @Carl: $L(G)$ is not complete, but it contains a complete subgraph of the same size (all the edges containing some particular vertex). $\endgroup$ – Eric Wofsey Jan 23 '15 at 10:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.