2
$\begingroup$

Why is the $W_6$ wheel graph not a line graph? I know a line graph of an undirected graph $G$ represents the adjacencies between edges of $G$.

If I assume that $W_6$ is a line graph, where is the contradiction that it cannot represent the adjacencies between edges of any graph (i.e. such a graph $G$ does not exist such that $W_6$ is its corresponding line graph)?

W6 Wheel Graph

$\endgroup$
2
$\begingroup$

Suppose that there is a graph $G$ such that its line graph $L$ is isomorphic to $W_6$.

Notice $G$ has an edge $e$ that is adjacent to exactly $5$ edges, after we remove this edge from the graph we obtain a graph $G'$ such that its line graph is isomorphic to a cycle. It is easy to show that if the line graph of a graph $H$ is a cycle then $H$ is isomorphic to the same cycle. To see this notice that since the line graph of $H$ contains a cycle then $H$ must also contain a cycle $C$, also $H$ must be connected, now notice that no extra edge can be joined to $C$, as this would force a vertex of the line graph to have degree exceeding $2$, so $H$ is equal to $C$.( this can be generalized, see here)

We conclude that $G$ must be isomorphic to the cycle $C_5$ along with a diagonal, but this clearly does not work.

$\endgroup$
0
$\begingroup$

Let $G$ be a graph with $L(G)$ isomorphic to $W_6$. Since $W_6$ has exactly 6 vertices, $G$ has exactly 6 edges. One vertex in $W_6$ is adjacent to all 5 other vertices, so one edge $e$ of $G$ is adjacent to all 5 other edges of $G$. The remaining vertices of $W_6$ have degree 3, thus the remaining edges of $G$ are adjacent to exactly 3 other edges.

By the pigeonhole principle, one endpoint $v$ of $e$ is incident with at least 3 other edges of $G$. Since those edges are adjacent to exactly 3 edges, $v$ must be incident with exactly 3 other edges of $G$, and those edges are adjacent only to each other and to $e$. But then the other endpoint $w$ of $e$ is incident with exactly 2 other edges of $G$, and those edges are adjacent only to each other and to $e$, a contradiction, since those edges must be adjacent to exactly 3 edges.

graph

$\endgroup$

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.