0
$\begingroup$

Prove that if $G$ contain an Eulerian circuit, then its line graph $L(G)$ also contains an Eulerian circuit.

Attempt:

Assume that the graph as undirected graph

then the vertice are $1,2,3,4,5,6,7$

Let $G$ be the graph with edge $(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,1)$

Apparently graph and its line graph that both will contain Eulerian circuits.

But I don't have any idea to prove it, Could you guys to help me ?

$\endgroup$
1
$\begingroup$

The proof is pretty easy:

Theorem: A connected graph $G$ has Euler cycle if and only if every vertex of $G$ is of even degree.

It easy to see that if all vertices of $G$ has even degree, then all the vertices of $L(G)$ has even degree (since each edge in $G$ is connected to odd number of edges from each of its two ends"vertices", and the sum of two odd numbers is even: $(2p+1) + (2q+1) = 2(p+q+1)$).

Now using the above Theorem we have the result for $L(G)$.

$\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.