Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
1  
In fact this is the only counterexample. en.wikipedia.org/wiki/… –  sdcvvc Oct 16 '12 at 17:32
    
That's amazing! –  Craig Feinstein Nov 30 '12 at 19:00
    
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. –  Douglas S. Stones Jan 6 '13 at 6:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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