Welcome to our community

Be a part of something great, join today!

Eulerian Circuits

Joystar1977

Active member
Jul 24, 2013
119
Consider the complete graph with 5 vertices, denoted by K5.

D.) Does K5 contain Eulerian circuits? (why?) If yes, draw them.

I know that Eulerian circuits are a circuit that uses every edge of a graph exactly once. These type of circuits starts and ends at the same vertex. If I find that the K5 has Eulerian circuits, then would I draw this on the graph in an oblong square shape? If I find that it doesn't wouldn't it have to do with the isomorphic representation because of the edges being counted twice?
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
As for whether $K_{5}$ has an Euler circuit, just look at whether it's connected, with all vertices of even degree. Then, if you want to draw the circuit, you can label the edges and then notate the path.
 

Joystar1977

Active member
Jul 24, 2013
119
Consider the complete graph with 5 vertices, denoted by K5.

Does K5 contain Eulerian circuits? (Why?) If yes, draw them.

Is it correct to say that K5 doesn't contain Eulerian circuits because all the vertices are not of even degree?
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
Is it correct to say that K5 doesn't contain Eulerian circuits because all the vertices are not of even degree?
What is the degree of each vertex?
 

Joystar1977

Active member
Jul 24, 2013
119
I am not sure about what the degree of each vertex really is. I do know that Kn has N vertices. Each vertex has degree N-1. The sum of all degrees is N (N - 1). I do know that there is a complete graph with 5 vertices denoted by K5.

What is the degree of each vertex?
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
I am not sure about what the degree of each vertex really is. I do know that Kn has N vertices. Each vertex has degree N-1. The sum of all degrees is N (N - 1). I do know that there is a complete graph with 5 vertices denoted by K5.
Perfect; I think you're sitting right on top of your answer. So $K_{5}$ has $5$ vertices. Based on what you just wrote, what is the degree of each vertex in $K_{5}$?
 

Joystar1977

Active member
Jul 24, 2013
119
Ackbach:

Am I suppose to add all the vertices in order to get the answer for what the degree of each vertex is in K5?

1 + 2 + 3 + 4 + 5 = 15

Is this correct?
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
No, you don't want to add up the vertex numbers. That would have no meaning. What is your goal here? Stay focused on that goal.
 

Joystar1977

Active member
Jul 24, 2013
119
Ackbach: I don't quite understand and was trying to guess at what I am suppose to do. This textbook really sucks that I have for this course doesn't give any examples and no dictionary in the back of the book.

Consider the complete graph with 5 vertices, denoted by K5.

Does K5 contain Eulerian circuits? (Why?) If yes, draw them.

I am not sure about what the degree of each vertex really is. I do know that Kn has N vertices. Each vertex has degree N-1. The sum of all degrees is N (N - 1). I do know that there is a complete graph with 5 vertices denoted by K5.

I am completely lost and don't understand.
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
Substitute the value for $n$ that you have. You know that $K_{n}$ has $n$ vertices, each of degree $n-1$. So $K_{5}$ has how many vertices? Each of them has what degree? (Just plug in what $n$ is for this case!) And what does the degree of each vertex tell you about whether $K_{5}$ has an Euler circuit?
 

Joystar1977

Active member
Jul 24, 2013
119
Please be patient while I try to understand this material. First, you say to substitute the value for n that you have. I have no idea what the value of n is and all I see is a numerical value for the vertices which is 5. I thought that in order to get the degree your suppose to add (v1, v2), v3, v4, v5) and then divide by 2. What do you mean by asking, "Each of them has what degree?" I do not understand you or what your asking me. How am I suppose to plug in something for n when there is no value for N? That doesn't make one bit of sense to me.
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,191
I think there might have been some confusion because there was an uppercase $N$ and a lowercase $n$. Let's just stick to lowercase $n$.

Definition: $K_{n}$ is the complete graph with $n$ vertices. Complete means that every pair of vertices is connected by an edge. You can see the first seven complete graphs here.

Now $K_{5}$ is the complete graph with five vertices. So if we're comparing $K_{n}$ with $K_{5}$, we would say that $n=5$ for this particular complete graph.

Now the degree of a vertex in a graph is the number of edges connected to the vertex. If you have a pictorial representation of a graph, then for any vertex, all you have to do to find the degree of each vertex is count the number of edges going into it.

You have also said that the degree of every vertex in $K_{n}$ is $n-1$. So what would the degree of every vertex in $K_{1}$ be? How about $K_{2}$? How about $K_{3}$? $K_{4}$? $K_{5}$?

Finally, an indirected graph has an Euler circuit if and only if every vertex has even degree, and the graph is connected. Are both of these conditions satisfied for $K_{5}$? If so, could you construct an Euler circuit for $K_{5}$?
 

Joystar1977

Active member
Jul 24, 2013
119
I am not trying to confuse myself even more with the uppercase N or the lowercase n. I will stick with the lowercase n. K5 is a complete graph that has 5 vertices. Why are you comparing Kn with K5? What do you mean by count the number of edges going into it? Are you suppose to count the number of edges going into K5 or Kn? What do you mean by asking me the degree of K1, K2, K3, K4, and K5?

I am not sure about what the degree of each vertex really is. I do know that Kn has N vertices. Each vertex has degree n-1. The sum of all degrees is n(n - 1). I do know that there is a complete graph with 5 vertices denoted by K5.

I am totally and completely lost. Just so you know I do have a learning disability which is Epilepsy Seizures. This causes me to have a hard time comprehending and understanding things. Please explain this in a different way because I am not understanding you. I don't know if the conditions are satisfied for K5. I am not sure whether or not I could construct a Eulerian circuit for K5.
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
I am not trying to confuse myself even more with the uppercase N or the lowercase n. I will stick with the lowercase n. K5 is a complete graph that has 5 vertices. Why are you comparing Kn with K5? What do you mean by count the number of edges going into it? Are you suppose to count the number of edges going into K5 or Kn? What do you mean by asking me the degree of K1, K2, K3, K4, and K5?
I am not sure about what the degree of each vertex really is. I do know that Kn has N vertices. Each vertex has degree n-1. The sum of all degrees is n(n - 1). I do know that there is a complete graph with 5 vertices denoted by K5.
Please study this webpage..

In the graph \(\displaystyle K_n\) there are \(\displaystyle n\) vertices; there are \(\displaystyle \frac{n(n-1}{2}\) edges; and each vertex has degree \(\displaystyle n-1\).

Therefore, if \(\displaystyle n\) is odd then \(\displaystyle K_n\) has an Euler Circuit.

Thus \(\displaystyle K_5\) does and \(\displaystyle K_8\) does not.