Welcome to our community

Be a part of something great, join today!

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

buchi

New member
Aug 10, 2013
2
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
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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\)

Untitled.gif

You can also use this webpage to help you.

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

buchi

New member
Aug 10, 2013
2
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?
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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.

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.
 

caffeinemachine

Well-known member
MHB Math Scholar
Mar 10, 2012
834
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!$