Does the graph G’ has a Euler circuit

discrete mathematicsgraph theory

We have the bipartite graph $G=K_{5,9}$.

We construct a new graph $G'$ by adding a new vertex $u$ that is connected with each vertex of $G$.

Then $G'$ has an Euler circuit, because every vertex has an even degree (the degree of $u$ is $5+9=14$, the degrees of the old vertices in the new graph $G'$ are $9+1=10$ and $5+1=6$ respectively) and $G'$ is connected.

Is this correct? Or doesn't $G'$ have an Euler circuit?

Best Answer

Yes, it's correct. A graph has an Euler circuit if and only if it satisfies the following two conditions: every vertex has even degree, and there is only one non-empty component. This graph is clearly connected, and the degrees are even as you say.

Related Solutions

[Math] Which of the following graphs has an Eulerian circuit

Here is a $2$-regular graph that is not connected:

             o---o   o---o  
             |   |   |   |  
             o---o   o---o

Your reasoning about (b) and (c) is correct; (c) is the only one that must have an Euler circuit.

[Math] Is it possible disconnected graph has euler circuit

Here we go: $$\huge\cdot\qquad\cdot$$

remember that $0$ is even. The circuit is the "empty circuit"
Since the graph has no edges, we've already passed every edge if we don't even move :D

Best Answer

Related Solutions

[Math] Which of the following graphs has an Eulerian circuit

[Math] Is it possible disconnected graph has euler circuit

Related Question