Combinatorics question: Lexicographic Topological sort of De Bruijn sequence after removing edges

I am self-learning an Algorithms course with a friend, and we are struggling to understand the answer to a question we were trying to solve for a couple of days. The question slightly involves a De Bruijn sequence, which I will explain at the bottom of the post what it is as it's not too well-known. The main part we don't understand is specifically combinatorics, however.

QUESTION:

Given a De Bruijn graph, prove that it is sufficient to remove $$\frac{k^n+k}{2}$$ edges to produce a topological sort of the graph which is also in lexicographical order.

First, we wish to remove all self-loops, as topological sort does not allow cycles; In any such graph there would be $$k$$ such edges (words containing only a single type of letter, e.g 11111 or 00000).

After this, we would wish to remove any edge which connects a vertex to a vertex which precedes it in lexicographical order. Unfortunately, this is where we are stuck; we weren't able to figure out how to calculate how many such edges exist. After eventually looking at the answers, apparently the answer is "exactly half of the remaining edges" ($$\frac{k^n-k}{2}$$) which, when we add to it the $$k$$ edges we removed earlier, arrives at the previous answer.

Now, while I recognize that usually dividing by two in combinatorics is due to duplicates of some sort, which implies symmetry, we still can't figure out the mathematical explanation for how/why the number of edges in a De Bruijn graph which break topological+lexicographical sort is exactly half. If anyone can explain how this comes about, I would highly appreciate it!

DE BRUIJN EXPLANATION:

For a given alphabet of $$k$$ letters and a word length of $$n$$, there are $$k^n$$ possible word combinations; a De Bruijn graph is, essentially, a directed connected graph from which all of these possible words in this language can be made: each edge is a 'word' in this language (word of length n made of k letters), and the vertices are all of the words of length $$n-1$$, so $$k^{n-1}$$ vertices in total. These graphs can be used to make a "De Bruijn Sequence", which is a cyclic string of letters from which all words of the above mentioned $$k$$, $$n$$ can be made, via Euler cycles.

For example, here is a De Bruijn graph and three of its respective sequences (which is really just the same sequence just shifted forwards, as it's cyclic. Note that a De Bruijn graph is not necessarily complete, that's just the case here:

De Bruijn Graph Illustration, for alphabet {0,1} (k=2),n=2

A respective De Bruijn sequence for this graph would be 0110; note that if we copy and shift this cyclic sequence by 1 $$k-1$$ times, we can quickly get all the possible words, and that a sequence is of length $$k^n$$:

0110
0011

that is, note the columns of this form all the possible words for the given k, n.

An edge corresponding to the word $$w_1 w_2 \dots w_n$$ should be removed if $$w_2 w_3 \dots w_n \preceq w_1 w_2 \dots w_{n-1},$$ where $$\preceq$$ denotes the lexicographic order. When does this happen? There are several cases:

• When $$w_2 < w_1$$.
• When $$w_2 = w_1$$ and $$w_3 < w_2$$.
• When $$w_2 = w_1$$ and $$w_3 = w_2$$ and $$w_4 < w_3$$.
• ...
• And so on up until the last case, where $$w_1 = w_2 = \dots = w_{n-1}$$ and $$w_n < w_{n-1}$$.
• Wait, no, the last last case is loops, which is where $$w_1 = w_2 = \dots = w_n$$.

How many edges correspond to each case? Let's look at the $$i^{\text{th}}$$ case, where $$w_1 = w_2 = \dots = w_i$$, $$w_{i+1} < w_i$$, and further letters (if they exist) are unconstrained. For $$i=1, 2, \dots, n-1$$, there are $$\binom k2$$ ways to choose $$w_i$$ and $$w_{i+1}$$. This determines the choice of $$w_1, \dots, w_{i-1}$$ as well. Then there are $$k^{n-i-1}$$ ways to choose $$w_{i+2}, \dots, w_n$$. (The $$i=n$$ case is loops, which we count separately.)

Altogether, the non-loop cases add up to $$\sum_{i=1}^{n-1} \binom k2 k^{n-i-1} = \frac{k(k-1)}{2} \sum_{i=1}^{n-1} k^{n-i-1} = \frac{k(k-1)}{2} \left(k^{n-2} + k^{n-3} + \dots + k + 1\right).$$ By the formula for the sum of a finite geometric series, this simplifies to $$\frac{k(k-1)}{2} \cdot \frac{k^{n-1} - 1}{k-1} = \frac{k(k^{n-1}-1)}{2} = \frac{k^n - k}{2}.$$ Adding the loops back in, we get $$\frac{k^n+k}{2}$$ as our final answer.

Or, we could count the non-loop cases by the following symmetry argument. All of the non-loop edges we remove can be characterized in the following way: not all of $$w_1, w_2, \dots, w_n$$ are equal, and at the first position where $$w_i \ne w_{i+1}$$, we have $$w_i > w_{i+1}$$.

By symmetry, there is an equal number of edges where not all of $$w_1, w_2, \dots, w_n$$ are equal, and at the first position where $$w_i \ne w_{i+1}$$, we have $$w_i < w_{i+1}$$. Together, these add up to the edges where not all of $$w_1, w_2, \dots, w_n$$ are equal, and there are $$k^n-k$$ such edges. Half of these, or $$\frac{k^n-k}{2}$$, have $$w_i > w_{i+1}$$ at the first position where $$w_i ne w_{i+1}$$.