Does the graph contain a Hamiltonian and an Euler cycle?

Question

Question:

Let $G=(V_n,E_n)$ such that:

• G's vertices are words over $\sigma=\{a,b,c,d\}$ with length of $n$, such that there aren't two adjacent equal chars.
• An edge is defined to be between two vertices that are different by only one char.

A. Does the graph contain an Euler cycle?

• Find a pattern.

B. Does the graph contain a Hamiltonian cycle

• This can be proven by induction.

---

$Solution.A.$

Now, when $n=1$, we have 4 vertices: $$v_1= \ 'a'$$ $$v_2= \ 'b'$$ $$v_3= \ 'c'$$ $$v_4= \ 'd'$$

Therefore, for each $v\in \{v_1,v_2,v_3,v_4\}$, $N(v)=\{v_1,v_2,v_3,v_4\}/ \{v\}$ so we get that their degree is 3, so by a theorem we get that there isn't an Euler cycle.

In addition, when $n=4$, considering the string $"abad"$ we have 2 options to replace the edges of the string. In order to replace the second char we have 2 options, replacing it by $'c'$ and $'d'$. For the third char, we can replace it only by $'c'$. In total, we got 7 edges with this vertex, so by a theorem, we get that there isn't an Euler cycle.

I cannot find here a pattern, because if we take a look at $n=2$ we get an Euler cycle.

$Solution.B.$

First, we examine whether each vertex has at least $\frac{n}{2}$ neighbors. Hence, we should take the vertex to have the least number of neighbors. This vertex should be the string with disjoint chars. i.e. the string "abcd" when $n=4$. The first and last chars has always 2 neighbors, so we get that the least degree is: $$2+2+\binom{n-2}{n-3} \cdotp 1=4+n-2=n+2\geq \frac{n}{2}$$

Thus, we get that the graph always has a Hamiltonian cycle.

---

I don't get why I didn't get a pattern in $A$, and how $B$ can be proven by induction. In addition, is my answer correct?

Answer 1

Your solution B doesn't work. The graph $G_n$ has $4\cdot3^n$ vertices rather than $n$ vertices, so you'd need to show each vertex had $4\cdot 3^n/2$ vertices to apply Dirac's theorem.

Answer 2

Claim: For $n > 3$, the graph $G = (V_{n},E_{n})$ has no Euler cycle.

When $n$ is even, we consider the string $w = a_{1}a_{2}...a_{n}$ with $a_{2i - 1} = a$ for $i = 1, 2,....,k$, $a_{2} = b$, and $a_{2i} = c$ for $i = 2,...,k$.

Then we see that $w$ has an odd degree. There's only one word that differ from w at $a_{3}$. This is because $a_{2} = b$ and $a_{4} = c$. There's two words that differ from w at $a_{1},a_{n}$. There's two words that differ from w at $a_{i}$ where $i \not = 3$. This is because for $a_{i - 1} = a_{i + 1}$ when $i \not 3$. Hence, there are $2(2k-1) + 1$ neighbors of w. The graph has no Euler cycle.

When $n$ is odd, consider the string $w = b_{1}b_{2}...b_{n}$ with $b_{2i - 1} = a$ for $i = 1,2,...,k + 1$. $b_{2} = b$, and $b_{2i} = c$ for $i = 2,3,...,k$. By the same argument as above, w has odd degree. The graph contains no Euler cycle.

For $n = 3$, the word $bac$ has degree 5.

Problem B: The graph as defined as $4*3^{n - 1}$ vertices for all $n \in \mathbb{N}$. We will show that for all $n > 1$, there exists a word with degree less than $2*3^{n - 1}$.

For $n = 2k$ even, let $w = a_{1}...a_{2(k - 1)}$ be a word such that $a_{i} \not a_{i + 2}$ for $i = 1,..., 2(k - 2)$ with $a_{i} \not = a$ for any $i$. Then the word $awa$ has $4 + 2(k - 1)$ neighbors.

For $n = 2k + 1$, then let $w = a_{1}...a_{2k - 1}$ be a word such that $a_{i} \not = a_{i + 2}$ for $i = 1,...,2k - 3$ with $a_{i} \not = a$ for any $i$. Then the word $awa$ has $4 + 2k - 1$ neighbors.

In both instances, for $a_{i}$ a character in $w$, it can only be replaced by one other character because $a_{i - 1} \not a_{i + 1}$.

Since, $4 + 2(k - 1) < 2*3^{2k - 1}$ for $k \geq 1$ and $4 + 2k - 1 < 2*3^{2k}$ for $k \geq 1$.

Answer 3

For part A use the words

$$w = a(bc)^k$$

and

$$w = a(bc)^kb$$

for $n>2$ odd and even respectively.

These have odd degrees since the first $b$ is the only letter that can be changed to only $1$ other. All others can be changed to $2$. By symmetry you get too many odd degree vertices for the graph to be Eulerian.

(This fails in the case $n=2$ when that $b$ becomes an "edge letter".)

EDIT: I'll put my code here for safe keeping:

import itertools

def makeGraph(n):
    letters = ['a', 'b', 'c', 'd']
    forbids = [c*2 for c in letters]
    g = Graph()
    for t in itertools.product(*[letters]*n):
        v = "".join(t)
        if all(f not in v for f in forbids):
            g.add_vertex(v)
    V = list(g.vertices())
    for v1 in V:
        for v2 in V:
            if sum(1 if c1!=c2 else 0 for c1,c2 in zip(v1,v2))==1:
                g.add_edge(v1, v2)
    return g


g = makeGraph(3)
g.show()

#for hc in g.subgraph_search_iterator(graphs.CycleGraph(g.order())):
#    print (hc)

found, hCyc = g.hamiltonian_cycle(algorithm='backtrack')
print(hCyc)