Skip to main content
added 4 characters in body
Source Link
Eric Wofsey
  • 31.2k
  • 2
  • 115
  • 151

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 uncountable connected graph whose cardinality $\kappa$ has uncountable cofinality works, since such a connected uncountable graph of cardinality $\kappa$ must havecontain a vertex of degree $\kappa$, and thus $L(G)$ contains a clique of size $\kappa$.

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 uncountable connected graph works, since a connected uncountable graph of cardinality $\kappa$ must have a vertex of degree $\kappa$, and thus $L(G)$ contains a clique of size $\kappa$.

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$.

Source Link
Eric Wofsey
  • 31.2k
  • 2
  • 115
  • 151

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 uncountable connected graph works, since a connected uncountable graph of cardinality $\kappa$ must have a vertex of degree $\kappa$, and thus $L(G)$ contains a clique of size $\kappa$.