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

  • Thread starter Thread starter buchi
  • Start date Start date
  • Tags Tags
    Circuits
AI Thread Summary
K5 contains Eulerian circuits, and the discussion revolves around how to systematically draw and count all possible circuits. Participants explore starting points and paths, questioning if there is a formula to determine the number of circuits in K_n. WolframAlpha is suggested as a useful tool for visualizing circuits, but clarity on its functionality is needed. The conversation also highlights the complexity of ensuring all circuits are accounted for, with a mention that the number of Eulerian circuits in K_n is divisible by n!. Understanding these circuits requires a grasp of graph theory principles.
buchi
Messages
8
Reaction score
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
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.
$$12345241351$$

View attachment 1157

You can also use this webpage to help you.

Change the five to say 9 and click the $$\boxed{=}$$.
 

Attachments

  • Untitled.gif
    Untitled.gif
    2.2 KB · Views: 123
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?
 
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 $$1231541~$$ there is no way to finish.

BUT $$12314524351$$ is a different Eulerian circuit from the one I posted.
 
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!$
 

Similar threads

Replies
13
Views
5K
Replies
4
Views
2K
Replies
1
Views
2K
Replies
5
Views
2K
Replies
2
Views
5K
Replies
2
Views
2K
Replies
8
Views
964
Back
Top