1
$\begingroup$

A triforce for the purposes of this question is a plane figure with an equilateral triangle at its center, with one additional vertex connected to each pair of original vertices (forming an additional equilateral triangle. This figure appears in games such as the classic Playstation game Tactics Ogre. How many Eulerian circuits are there for this figure, and what changes if you consider ways in which circuits might be equivalent (reversal, rotation, reflection)?

This is related to this question about ways to draw a complete graph but we are asking for circuits rather than paths.

For instance, drawing of a cycle this is a potential circuit, but I could have shown us starting from B instead, or starting from c in two different ways and it would still be the same circuit.

$\endgroup$

1 Answer 1

2
$\begingroup$

Warning: this is a self-answer with major spoilers for one interpretation of the question (all symmetries) - it's different if you don't allow reflections because you can't reflect a piece of paper.

If we use all symmetries, there are

only 5 circuits

Approach:

When we try to look for different ways things might be structured we want to look for invariants - properties of a circuit that don't change when we rotate/reverse/reflect. There are a few that we can take advantage of here. One is that we have three degree-4 nodes (a, b, c in the diagram) and three degree-2 nodes (A, B, C). You can't go from a degree-2 node to another one, so they have to split the 6 times you visit a degree-4 node.

Another is that when you approach and leave a degree-4 node you can have a circuit which intersects itself (if you do A-c-a + B-c-b, for instance) or two ways to not intersect yourself (A-c-B + a-c-b vs A-c-b + a-c-B).

Solution:

Every circuit is equivalent to one of:

1. 444424242 (visiting 4 degree-4 nodes in sequence), non-self-intersecting.
Representative: acbaCbAcB

2. 444424242 (visiting 4 degree-4 nodes in sequence), self-intersecting.
Representative: bCaBcbacA

3. 444244242 (one sequence of 3 degree-4 nodes). This has to approach each of the degree-4 nodes in a different one of the three ways mentioned above.
Representative: aBcabAcbC

4. 442442442 (three sequences of 2 degree-4 nodes). Self-intersecting three times.
Representative: BabAcaCbc* I missed this one in my pen-and-paper enumeration and only noticed after computationally checking

5. 442442442 (three sequences of 2 degree-4 nodes). Self-intersecting twice.
Representative: aBcbCabAc

Illustrations: Link (Please note that upper/lowercase are inverted in the diagram at the top of the image.)

Computational verification:

Colab worksheet with demos

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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