6
$\begingroup$

Suppose I am given a line graph $L(G)$, but don't know $G$. Is it possible for me to determine from this information whether $G$ is bipartite?

$\endgroup$

1 Answer 1

6
$\begingroup$

I originally thought the answer was yes which is why I posted the question, but I found that it's no.

Let $G$ be such that $E(G)=\{ \{1,2\},\{2,3\},\{1,3\}\}$ and $V(G)=\{1,2,3\}$. Then the line graph is of the form $V(L(G))=\{a,b,c\}$ and $E(L(G))=\{\{a,b\},\{b,c\},\{a,c\}\}$.

The complete graph $K_3$ and its line graph.

Let $H$ be such that $E(H)=\{\{1,2\},\{1,3\},\{1,4\}\}$ and $V(H)=\{1,2,3,4\}$. Then the line graph is of the form $V(L(H))=\{a,b,c\}$ and $E(L(H))=\{\{a,b\},\{b,c\},\{a,c\}\}$.

The complete bipartite graph $K_{1,3}$ and its line graph.

$G$ is not bipartite, but $H$ is bipartite, yet they have the same line graph.

$\endgroup$
3
  • 2
    $\begingroup$ In fact this is the only counterexample. en.wikipedia.org/wiki/… $\endgroup$
    – sdcvvc
    Commented Oct 16, 2012 at 17:32
  • $\begingroup$ That's amazing! $\endgroup$ Commented Nov 30, 2012 at 19:00
  • $\begingroup$ This is the only connected counterexample. For example "two copies of $G$" (not bipartite) and "two copies of $H$" (bipartite) have the same line graph too. $\endgroup$ Commented Jan 6, 2013 at 6:12

You must log in to answer this question.

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