MHB Ans: Eulerian Circuits in K5 Graph: Does it Exist?

[Joystar77]

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]

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.

 

[Joystar77]

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]

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?

 

[Joystar77]

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]

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}$?

 

[Joystar77]

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]

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.

 

[Joystar77]

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]

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?

 

[Joystar77]

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]

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}$?

 

[Joystar77]

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.

 

[Plato2]

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 $$K_n$$ there are $$n$$ vertices; there are $$\frac{n(n-1}{2}$$ edges; and each vertex has degree $$n-1$$.

Therefore, if $$n$$ is odd then $$K_n$$ has an Euler Circuit.

Thus $$K_5$$ does and $$K_8$$ does not.