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

  • MHB
  • Thread starter buchi
  • Start date
  • Tags
    Circuits
In summary: Conversely, let $v_1,\ldots,v_{n+1}$ be an Eulerian circuit in $K_n$, then $v_{n+1},\ldots,v_1$ is too. So, we have a total of $(n+1)!/2$ Eulerian circuits in $K_n$.In summary, there is no systematic way of listing all the Eulerian circuits in $K_n$, but the number of such circuits in $K_n$ is $(n+1)!/2$.
  • #1
buchi
9
0
how would one possibly draw all the possible Eulerian circuits? the way I am thinking of it is if we start say at vertex 1 and go through each vertex and edge and come back to vertex 1 then we can do the same for each vertex up to 5 but then we can also start at vertex one and head a different way to arrive at the same vertex so I guess my question is is there a systematic way to calculate how many different paths we could take? and to draw them? would we just draw exactly the same picture however many times and putting an arrow showing the path?

Thanks
 
Physics news on Phys.org
  • #2
buchi said:
how would one possibly draw all the possible Eulerian circuits? the way I am thinking of it is if we start say at vertex 1 and go through each vertex and edge and come back to vertex 1 then we can do the same for each vertex up to 5 but then we can also start at vertex one and head a different way to arrive at the same vertex so I guess my question is is there a systematic way to calculate how many different paths we could take? and to draw them? would we just draw exactly the same picture however many times and putting an arrow showing the path?

Here is one Eulerian circuit Look at the graphic.
\(\displaystyle 12345241351\)

View attachment 1157

You can also use this webpage to help you.

Change the five to say 9 and click the \(\displaystyle \boxed{=}\).
 

Attachments

  • Untitled.gif
    Untitled.gif
    2.2 KB · Views: 68
  • #3
Thanks for that plato, but I get what you mean there but i am just curious if there is a systematic way to make sure i haven't missed any circutes or is there a general formula to work out how many Eulerian circuits are in K_n?? could you do say K_4 as an example and list the different circuits.

also you said change the 5 say to 9 and click the ___? i can't see what symbol that is on your reply and what you mean by that sentence?
 
  • #4
buchi said:
also you said change the 5 say to 9 and click the ___? i can't see what symbol that is on your reply and what you mean by that sentence?
I don't know anything about your computer/browser. But I was talking about the Wolframalpha in the link.
At the end of the input window there is a = sign that acts like a return key.
Wolframalpha is a wonderful resource for mathematics students. You should learn to use it.
It is available on most mobile devices in both popular formats.

buchi said:
I get what you mean there but i am just curious if there is a systematic way to make sure i haven't missed any circutes or is there a general formula to work out how many Eulerian circuits are in K_n?? could you do say K_4 as an example and list the different circuits.

I have never done research in graph theory. I have taught many undergraduate courses that include graph theory as at least a third of the course. That said, I am not qualified to comment on a systematic way to make sure of any listing or even counting of Eulerian circuits from any particular vertex.

I will point out that if we begin \(\displaystyle 1231541~\) there is no way to finish.

BUT \(\displaystyle 12314524351\) is a different Eulerian circuit from the one I posted.
 
  • #5
Plato said:
That said, I am not qualified to comment on a systematic way to make sure of any listing or even counting of Eulerian circuits from any particular vertex.
Hey Plato.

You raise an interesting question of counting the number of Eulerian circuits in $K_n$. Here are my first thoughts. Let $v_1,\ldots,v_k$ be an Eulerian circuit in $K$. Then $v_{\sigma(1)},\ldots,v_{\sigma(k)}$ too is an Eulerian circuit in $K_n$ for each $\sigma\in S_n$. So the number of Eulerian circuits in $K_n$ is divisible by $n!$
 

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

1. What is an Eulerian circuit?

An Eulerian circuit is a path that visits every vertex in a graph exactly once and ends at the starting vertex. It is named after the mathematician Leonhard Euler.

2. How do you determine if K5 contains Eulerian circuits?

K5, also known as the complete graph with 5 vertices, does contain Eulerian circuits. This can be determined by the fact that every vertex in K5 has a degree of 4, meaning that there are an even number of edges connected to each vertex.

3. Can you provide an example of an Eulerian circuit in K5?

One example of an Eulerian circuit in K5 is the path ABCDEA, where A, B, C, D, and E represent the 5 vertices in the graph and the edges connect them in the order of A to B, B to C, C to D, D to E, and E back to A.

4. Is it possible for K5 to contain more than one Eulerian circuit?

Yes, K5 can contain multiple Eulerian circuits. In fact, it can have a total of 120 different Eulerian circuits.

5. Can you draw all the possible Eulerian circuits in K5?

Yes, all the possible Eulerian circuits in K5 can be drawn. However, due to the large number of possible circuits, it would be impractical to list and draw them all. Instead, it is more efficient to use mathematical principles to determine the number of possible circuits in K5.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
13
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
478
  • Electrical Engineering
Replies
5
Views
1K
Replies
2
Views
373
Replies
7
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
4K
Replies
1
Views
2K
  • Special and General Relativity
Replies
5
Views
1K
Replies
4
Views
823
Back
Top