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?
Tell me more
×
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.
|
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\}\}$.
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\}\}$.
$G$ is not bipartite, but $H$ is bipartite, yet they have the same line graph. |
|||||||||
|

