Is Eulerian graph necessarily connected?

746 Views Asked by At

If a graph is Eulerian (i.e. has an Eulerian tour), then do we immediately assume for it to be connected?

The reason I ask is because I came across this question:

Graph and its line Graph that both contain Eulerian circuits

And the solution seems to assume that the graph is connected, before using the result that a connected graph is Eulerian if and only if every vertex has even degree.

2

There are 2 best solutions below

0
On BEST ANSWER

A graph $G$ with an Euler circuit need not be connected, but the subgraph induced by the vertices that are on the Euler circuit must be a connected component of $G$, and any other components must be isolated vertices. In the question to which you linked it doesn’t actually matter whether $G$ is connected: even if it has some isolated vertices, its line graph will be derived completely from the component with the Euler circuit and will therefore be connected.

0
On

We are given that the original graph has an Eulerian circuit. So each edge must be connected to each other edge, regardless of whether the graph itself is connected. Thus the line graph must be connected. Technically this ought to have been pointed out in the answer post you linked, yes.