0
$\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$
1
  • $\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$ – Morgan Rodgers Dec 23 '20 at 12:10
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$
0
$\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$

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.