Let $G$ be a simple, undirected and connected graph for which every vertex has degree $r$. Prove that the line graph $G'$ of $G$ is Eulerian.
So, basically we have two options for $r$, either it is even or odd. In the case that it is even, the problem is trivial, cause according to a theorem about Eulerian graphs, we have that a graph is Eulerian iff $\forall x \in V : d(x)$ is even.
Therefore, we have that $\forall v: |\Gamma(v)|$ is even, meaning even number of edges share this vertex. So, in return we will have a line graph with even degree ($d(e), e \in E$ even), so we will have an Eulerian graph.
But what happens if $r$ is odd?
Best Answer
If $r$ is even, then $G$ is Eulerian, but this doesn’t immediately tell you that $G'$ is Eulerian. What you need to show is that if every vertex of $G$ has the same degree, then every vertex of $G'$ has even degree.
It turns out that you don’t need to worry about whether $r$ is even or odd. Suppose that $e=\{u,v\}$ is an edge of $G$ and hence a vertex of $G'$; we want to show that $\deg_{G'}e$ is even. Suppose that $f=\{x,y\}$ is another edge of $G$ and vertex of $G'$; under what circumstances is $\{e,f\}$ an edge of $G'$? According to the definition of the line graph, $\{e,f\}$ is an edge of $G'$ if and only if the edges $e$ and $f$ of $G$ have a vertex in common. In other words, $G'$ has an edge between its vertices $e$ and $f$ if and only if $\{u,v\}\cap\{x,y\}\ne\varnothing$. This means that $\deg_{G'}e$ is the number of edges of $G$ (other than $e$ itself) that have $u$ or $v$ as a vertex.