1
$\begingroup$

From the way I understand it:

(1) a trail is Eulerian if it contains every edge exactly once.

(2) a graph has a closed Eulerian trail iff it is connected and every vertex has even degree

(3) a complete bipartite graph has two sets of vertices in which the vertices in each set never form an edge with each other, only with the vertices of the other set.

So by definition a bipartite graph has some edges that are not used (i.e. the edges between vertices of the same set). That would then mean that there are unused edges and so the graph cannot be Eulerian.

What am I missing here?

$\endgroup$
2
  • 2
    $\begingroup$ There aren't edges between vertices in the same set that "aren't used". There aren't edges of this type at all. $\endgroup$
    – xxxxxxxxx
    Dec 23, 2020 at 12:10
  • $\begingroup$ Notice that even cycles $C_{2n}$ are bipartite and (obviously) Eulerian. Moreover, if your interested only in complete bipartite graphs $K_{p,q}$, then notice that such a graph has $p$ vertices of degree $q$ and $q$ vertices of degree $q$, whence, using (2), $K_{2n,2m}$ is both bipartite (by construction), connected, and has all vertices of even degree, thus is Eulerian. $\endgroup$
    – thibo
    Apr 26, 2021 at 15:23

2 Answers 2

Reset to default
2
$\begingroup$

Note that a graph is Eulerian if and only if it is connected and the degree of every vertex is even.

We can have many bipartite graphs with these properties.

For example $$k_{2,2}$$ is Eulerian.

Your confusion with the edges is that , you think we have to trace every potential edge in the graph as well as every edge which is actually an edge.

Note that you only have to trace the edges that exist not the potential edges which could be made by joining vertices which are not connected at this point of time.

$\endgroup$
0
$\begingroup$

When you say "a bipartite graph has some edges that are not used", you are not talking about graphs in the standard way. A trail is Eulerian if, in your terminology, it contains all edges "that are used in the graph".

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .