Question

If a complete graph having an Euler circuit has n vertices, the n could not be 2. What other values of n would be impossible?

Answer 1

"An Euler circuit is a circuit that uses every edge in a graph with no repeats. Being a circuit, it must start and end at the same vertex."
According to this source https://courses.lumenlearning.com/waymakermath4libarts/chapter/euler-circuits/#:~:text=An%20Euler%20circuit%20is%20a%20circuit%20that%20uses,must%20start%20and%20end%20at%20the%20same%20vertex.

Now I'm confused. Based on those rules, couldn't a Euler circuit exist with 2 nodes like the picture I drew? Or is that specifically not allowed?

Answer 2

Based on what I read, it seems like it's more important how many *connections* each vertex has, rather than the number of vertices itself. But this is a pretty new concept to me, so it's entirely possible I'm wrong about that.

Answer 3

Specifically, the article states that every vertex must have an even number of connections. This makes sense, because for every connection coming *into* the vertex, there must be a single connection coming *out of* the vertex, which requires an even number of connections. I didn't find anything about the number of vertices...

Answer 4

this is the complete question.

Answer 5

Ah, so it's specifically asking about "complete graphs", which the question defines as a graph where "every vertex is connected by [at least] one edge to each of the other vertices". I think that makes the question a bit clearer. Hmmm

Answer 6

Well, since I don't know much about the theory, let me just work it out manually...

Answer 7

Ok, I think I figured it out. Turns out, my earlier example with 2 vertices was wrong, because there's a redundant connection between the two vertices in that one, so it wouldn't count as "complete"

In fact, it seems that complete graphs with an even number of vertices cannot contain a Euler circuit. It is true, as I read, that Euler circuits must have an even number of connections for each vertex, but this would not be true for a complete graph with an even number of vertices.
In general, vertices of a complete graph will have n-1 connections (n being the total number of vertices), since each vertex has to connect to every other vertex (other than itself). That means, for a complete graph with an even number of vertices, each vertex will have an odd number of connections, meaning no Euler circuit.

In short, to answer the question, if n is even, there will not be a Euler circuit (in the complete graph)

Answer 8

Thank you, after reading about this for hours, your answer actually makes sense. You rock!

Answer 9

Thank you! I'm glad what I said made sense =D