3
$\begingroup$

The rules are very simple ...

  1. Star at A, end at A.

  2. From one point you can to go to the other point by only one line (no turning at cross roads).

  3. No going over any line more than once.

how many ways to draw

find the possible number of distinct eulerian paths that exist?

$\endgroup$
  • $\begingroup$ does crossing over the same point twice break rule 3? $\endgroup$ – Kyle He May 12 at 4:56
  • $\begingroup$ I read rule 2 as saying that you can only arrive at each point once ("by only one line"), because otherwise I cannot interpret rule 2 in a way that could be characterized as a rule, but I agree it is probably ambiguous and worth specifying $\endgroup$ – hdsdv May 12 at 5:11
  • 7
    $\begingroup$ Does this answer your question? How many different Paths exist in this journey? (See Jaap's answer and the comments below it...) $\endgroup$ – Stiv May 12 at 5:11
5
$\begingroup$

Edit 3: @Galen has now modified their answer accordingly. Good answer!


Edit 2: Even though the question has been closed as a duplicate, I thought for the sake of mathematics and posterity (and anyone happening to read this question and wonder why the accepted answer here is different to the accepted answer at the duplicate question - which is correct) I'd explain why @Galen's answer is off by a factor of $2$.

Initially (Edit 1) I assumed this was because @Galen's figure of $264$ did not count paths with the direction reversed separately, but this source makes it clear that $264$ is counting paths in the opposite direction twice (since they count $2$ paths in $K_3$).

This had me stumped for a while (especially since this answer uses a different method of counting by hand to mine and also arrives at $528$) until I realized that every Eulerian circuit in the graph 'passes through' $A$ twice so if we try to solve the problem by using the known number of Eulerian circuits, we need to count each one twice depending on which occurrence of $A$ in it we start at. For example, $ABCADBECDEA$, $AEDCEBDACBA$, $ADBECDEABCA$, and $ACBAEDCEBDA$ are four possible paths through the graph in the total of $528$ Eulerian paths starting and ending at $A$, but @Galen's method will only count two of them since the last $2$ can be obtained by shifting the first two sequences left to right.


Edit 1: The question has since been closed as a duplicate, but for the record, as it initially stood it appeared to ask for the number of directional paths. The answer here therefore is double the answer to the question as it stands.


It turns out we can solve this problem by hand. (While the fancy asymptotics may be useful for larger graphs, a five-vertex complete graph is simple enough to enumerate manually). I'll interpret the problem similarly to @Galen, because while I agree the OP's point $(2)$ is unclear, I think the only reasonable way to interpret their final sentence is to assume they were asking the following question:

How many ways are there of physically drawing the printed figure beginning at point $A$ and covering each edge exactly once?

which is equivalent to asking how many distinct paths through the graph there are beginning at $A$ and traversing every edge exactly once. This is an interesting question.

It turns out (unless I have made a mistake, which is possible), @Galen's enumeration of the Eulerian circuits is off by a factor of $2$ because in the physical example of drawing a picture, paths proceeding in the opposite direction are distinct. We can show the answer is:

$528$

by solving the problem by hand:

Note that due to symmetry, and the number of incident edges at each vertex being $4$, this is equivalent to finding a sequence of $11$ letters from $\{A,B,C,D,E\}$ beginning and ending with $A$ in which each letter (except $A$ which occurs thrice) occurs twice, and no subsequence $XY$ appears more than once in either direction (only one occurrence of either $XY$ or $YX$ for all $X,Y\in\{A,B,C,D,E\}$).

This is now a simple enumeration problem. We begin with $A$. There are $4$ options for the next element, and without loss of generality (by the symmetry of the problem), let it be $B$. There are $3$ options for the next element (since we cannot backtrack), and without loss of generality, let it be $C$. Now our decision tree branches.

Our first option is to return to a point we have already touched. The only possible such point is $A$. Next, we have $2$ possible points we can go to, neither of which we have visited yet. Without loss of generality, choose $D$. Our sequence so far (which stands in for $4\times3\times2=24$ global possibilities) is $ABCAD$ without loss of generality. From this point on, the decision tree is simple to construct because of the constraints of the problem, and we can easily deduce that this point has $6$ valid branches (remaining points $BECDEA$, $BEDCEA$, $CEBDEA$, $CEDBEA$, $EBDCEA$, $ECDBEA$).

Our second option is to visit a new point. There are $2$ possibilities here; without loss of generality, let it be $D$. Our sequence so far (which stands in for $4\times3\times2=24$ global possibilities) is $ABCD$ without loss of generality. From here on, the decision tree is again simple to enumerate, with $16$ possible branches (remaining points $ACEBDEA$, $ACEDBEA$, $AEBDECA$, $AEDBECA$, $BEACEDA$, $BEADECA$, $BECADEA$, $BECAEDA$, $BEDACEA$, $BADAECA$, $EACEBDA$, $EADBECA$, $EBDACEA$, $EBDAECA$, $ECADBEA$, $ECAEBDA$).

Thus the total number of possibilities is:

$(24\times6)+(24\times16)=528$

A graph of the decision tree is as follows, to aid in visualisation of the solutions:

Tree

| improve this answer | |
$\endgroup$
  • $\begingroup$ great work, the answer i was given is 264, but your explanation seems to contain an error somewhere $\endgroup$ – Shiv Prateek May 12 at 11:32
  • 1
    $\begingroup$ @ShivPrateek Fair enough! It would probably be worthwhile reproducing the wording of the question you got it from though, since $264$ (as Galen showed) is the number of Eulerian paths, but if you meant to ask for the number of ways to draw the image, that will be twice that (since you could follow each path in either direction). $\endgroup$ – Anon May 12 at 11:35
  • $\begingroup$ @ShivPrateek If you see the answer here, the author there also counted all directional paths and reached the same number ($528$). Incidentally, if this is what you are after, your question is a duplicate. $\endgroup$ – Anon May 12 at 11:49
  • $\begingroup$ @Anon Nice effort. I like your symmetry argument, and the decision tree. $\endgroup$ – Galen May 12 at 13:38
5
$\begingroup$

Short version:

The answer is 528, but I spend a few paragraphs considering Eulerian circuits.

Long version:

In this answer I'm going to interpret that the OP is asking for

the number of Eulerian circuits

for this 5-complete graph. If that's the case, we have to realize that this is not really a problem to readily be solved exactly by hand. If the OP will accept approximations, we can consider an asymptotic approach.

McKay and Robinson (1995) developed the following asymptotic formula that counts the paths described in the puzzle: https://wikimedia.org/api/rest_v1/media/math/render/svg/aa8ab72f32df5af0c823766b758725539382e561

Now the counting formula has a variable $\epsilon$ representing error, for which I'll consider the extreme cases where $\epsilon = \pm \infty$. When I plug in $n=5$ with the chosen error bounds, I get:

$ec(K_5) \in (258.11735947, \infty)$

which is to say that the answer is between

258.11735947 and $\infty$.

or even more simply

the answer is greater than 258.11735947

but to top it all off

Table 1 of this paper actually states that there are 264 Eulerian paths.

Errata

As @stiv pointed out in the comments of the original post, this puzzle is probably a duplicate of another puzzle. My original attempt assumes that the number of eulerian circuits is being asked for, however the duplicate illiminates a distinction between drawing and eulerian circuits Each line in such a circuit could have been drawn in one of two orders, and thus the correct answer is twice the value that I concluded above and therefore the correct answer is

528

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ +1 for the hard work :) $\endgroup$ – ABcDexter May 12 at 6:33
  • 1
    $\begingroup$ @Galen Nice work. I think the good old manual method showed your number was essentially correct, but highlighted a little problem if we interpret the OP as asking how many ways there are to draw the figure. See my answer... $\endgroup$ – Anon May 12 at 7:57
  • 1
    $\begingroup$ well done @Galen $\endgroup$ – Shiv Prateek May 12 at 11:33
  • 1
    $\begingroup$ @Galen I just realized the problem with your answer - your number is actually incorrect by a factor of $2$ because (even though as I have now realized your source number includes paths in the opposite direction twice), it does not account for the fact that rnpu Rhyrevna pvephvg cnffrf guebhtu $N$ gjvpr, fb gur ahzore bs Rhyrevna cnguf fgnegvat naq raqvat ng $N$ (juvpu vf jung gur BC vf nfxvat sbe, rira va gur zbqvsvrq dhrfgvba) vf gjvpr gur ahzore bs Rhyrevna pvephvgf va gur tencu nf n jubyr. Guhf gur nafjre gb BC'f dhrfgvba nf vg fgnaqf vf va snpg $528$ (nyfb sbhaq va gur qhcyvpngr dhrfgvba). $\endgroup$ – Anon May 12 at 20:51
  • 1
    $\begingroup$ @Anon Yup, you're right. I answered within a narrower context. $\endgroup$ – Galen May 12 at 22:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.