Suppose X and Y are graphs with minimum valency 4. Then X $\cong$ Y iff L(X) $\cong$ L(Y).

Question

I'm having trouble with this question. So I know that since X has no triangles (cliques of size 3), the cliques determined by the vertices of X in L(X) are maximal. How do I proceed?

Answer 1

It is clear that $X \cong Y$ implies $L(X) \cong L(Y)$. We need to prove the converse assuming that $X$ and $Y$ have minimum valency $4$.

Suppose $X$ and $Y$ are graphs with minimum valency $4$ and $L(X) \cong L(Y)$. The set of edges of $X$ incident to a vertex $u \in V(X)$ corresponds to a clique in $L(X)$ of size $4$ or more. Two such cliques in $L(X)$ have at most one vertex in common: if $u$ and $v$ are adjacent vertices in $X$, then the corresponding cliques in $L(X)$ have the vertex $uv$ in common; if $u$ and $v$ are non-adjacent vertices in $X$, then the corresponding cliques in $L(X)$ have no vertices in common.

If $X$ has $n$ vertices, then $L(X)$ has $n$ maximal cliques (each having size $4$ or more). There is a bijection between $V(X)$ and these maximal cliques of $L(X)$. Because $L(X)$ and $L(Y)$ are isomorphic, $L(Y)$ also has $n$ maximal cliques which satisfy the same intersection condition given in the previous paragraph for $L(X)$. This intersection condition along with the bijection between $V(Y)$ and maximal cliques of $L(Y)$ gives a one-to-one correspondence between $V(Y)$ and $V(X)$ which preserves adjacency and nonadjacency.

In other words, $a$ and $b$ are adjacent vertices in $X$ iff cliques $A$ and $B$ of $L(X)$ have a vertex in common iff cliques $A'$ and $B'$ of $L(Y)$ have a vertex in common iff $a'$ and $b'$ are adjacent vertices in $Y$.