Well, the exercise it's as the title says. I know that if $G$ is connected then for every pair of vertex $u,v$ in $G$ there's a walk between them. So when the Line Graph $L(G)$ is constructed those edges in $G$ where the walk between $u$ and $v$ is formed will be adjacent vertex in the Line Graph $L(G)$. Since $G$ is connected therefore $L(G)$ must be connected.

I'm not sure about if the argument is valid, also I'm looking for a more formal/detailed proof, because I think there's a lot of holes in this argument.


The argument given is correct, though a bit informal. Here's an elaboration:

To be more precise, suppose $G$ is connected. Then for any two vertices $u,v\in G$, there is a path $P=u\to x_1\to x_2\to\cdots\to x_n\to v$ where the $x_i$'s are some other vertices of $G$.

By the existence of such a path $P$, we can say that $u$ is adjacent to $x_1$, $x_i$ is adjacent to $x_{i+1}$ (for $1\leq i\lt n$) and $x_n$ is adjacent to $v$

By the definition of the line graph $L(G)$, this means $(u,x_1),(x_i,x_{i+1})$ and $(x_n,v)$ are vertices of $L(G)$ [for $1\leq i\lt n$]

Now, since $(u,x_1)$ and $(x_1,x_2)$ share a common endpoint $x_1$, they must be adjacent in $L(G)$. Similarly, $(x_i,x_{i+1})$ is adjacent to $(x_{i+1},x_{i+2})$ for $1\leq i\lt n-1$ and $(x_{n-1},x_n)$ is adjacent to $L(G)$

So, we have a path $L_P$ in $L(G)$ as $L_p=(u,x_1)\to (x_1,x_2)\to\cdots\to(x_{n-1},x_n)\to(x_n,v)$

Hence, for every path $P$ in $G$, there is a path $L_P$ in $L(G)$.

Suppose $(a,b)$ and $(A,B)$ are two vertices of $L(G)$. We show that there is a path between them: By definition of $L(G)$, all four of $a,b,A,B$ are vertices of $G$ with $a$ adjacent to $b$, ie, $a\to b$ and $A$ adjacent to $B$, ie, $A\to B$; since $G$ is connected, there must be a path $P_{bA}$ from $b$ to $A$ which translates to a path $L_{\large P_{bA}}$ in $L(G)$ which gives us a path $a\to b\to P_{bA}\to A\to B$ in $G$ and a path $(a,b)\to L_{\large P_{bA}}\to (A,B)$ in $L(G)$


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.