There are four types of legitimate sequence of length $n$:
Type $A$: the last four colours are distinct,
Type $B$: the second from last colour is repeated later in the sequence,
Type $C$: the third from last colour is repeated later in the sequence,
Type $D$: the fourth from last colour is repeated later in the sequence.
A length $n$ sequence of type $A$ may be extended uniquely to one sequence each of type $A,B,C,D$ of length $n+1$. Sequences of the other types may be extended uniquely to just one sequence of length $n+1$ of the following types:$$B\to C\to D\to A.$$
Let $A_n,B_n,C_n,D_n$ denote the number of length $n$ sequences of type $A,B,C,D$ respectively, each divided by 24 (to keep the numbers small). From the above we have:
\begin{eqnarray*}
A_{n+1}&=&A_n+D_n\\
B_{n+1}&=&A_n\\
C_{n+1}&=&A_n+B_n\\
D_{n+1}&=&A_n+C_n\\
\end{eqnarray*}
Writing $A_n,B_n,C_n,D_n$ as a column vector and starting at $n=4$ we get:
$$
\left(\begin{array}{c}
1\\1\\2\\3
\end{array}
\right)
\to
\left(\begin{array}{c}
4\\1\\2\\3
\end{array}
\right)
\to
\left(\begin{array}{c}
7\\4\\5\\6
\end{array}
\right)
\to
\left(\begin{array}{c}
13\\7\\11\\12
\end{array}
\right)
\to
\left(\begin{array}{c}
25\\13\\20\\24
\end{array}
\right)
\to
\left(\begin{array}{c}
49\\25\\38\\45
\end{array}
\right)
\to
\left(\begin{array}{c}
94\\49\\74\\87
\end{array}
\right)
$$
Adding the values for $n=10$ and returning the factor of 24 we get:$$24(94+49+74+87)=24*304=7296.$$
This was quick to do by hand for $n=10$. However the general solution will be a linear combination of $n$'th powers of the roots of the polynomial $$t^4-t^3-t^2-t-1.$$
In each of the $n$ colors, there are $\frac{n-1}{2}$ edges. For a fixed vertex $v$, the probability it's left uncovered by $e_1, \dots, e_n$ is the probability that for each of the $n-1$ colors occurring on edges out of $v$, we don't choose the edge with an endpoint at $v$, which is $(1 - \frac{2}{n-1})^{n-1}$. As $n \to \infty$, this approaches about $e^{-2}$.
If, for all $v$, the events "$v$ is uncovered" were independent, then the probability that all vertices are covered would approach $(1 - e^{-2})^n$, which is exponentially small. Of course, the events are not independent. But they're mostly independent: knowing $v$ is uncovered doesn't significantly affect the odds that $w$ is uncovered. So we might expect that the true probability is not too far from $(1-e^{-2})^n$.
In general, proving "these events are independent enough" is hard. But if all we want is a bound of $\frac1{n(n+1)}$, then there is enough of a gap between what we want and what ought to be true that we can give a lot away in the service of making our life easier. One way to do this is with a coupling argument. That is, we describe a larger probability space, within which we have:
- The original random process, where edges $\{e_1, \dots, e_n\}$ are sampled with the correct distribution;
- A different, easier-to-understand random process with more independence;
- Some relationship between the two processes.
Let $S$ be an arbitrary subset of $\sqrt n$ out of the $n$ vertices. To describe the coupling, we give a random alorithm that generates the set $\{e_1, \dots, e_n\}$, and simultaneously assigns a label to each vertex of $S$ that's an upper bound on the number of edges from $e_1, \dots, e_n$ incident on that vertex.
Initially, all labels start at $0$. For each color class $E_i$, we will go through the edges of $E_i$ one at a time in some order that deals with the edges with an endpoint in $S$ first. When we get to the $j^{\text{th}}$ edge in $E_i$ (call that edge $vw$), we do the following:
- Let $p=\frac1{k+1-j}$ if we have not selected $e_i$ yet, and let $p=0$ otherwise. This is the probability with which we want to set $e_i = vw$.
- If both $v$ and $w$ in $S$, then for each one, add $1$ to its label with probability $\sqrt{\frac 3n}$. If both of their labels increase by $1$ (which happens with probability $\frac 3n$), then with probability $\frac{p}{3/n}$, let $e_i = vw$. (Note that $p = \frac1{k+1-j}$ is at most $\frac1{k+1-\sqrt n} = \frac2{n+1-2\sqrt n} < \frac 3n$ for $n>30$ or so, so this is a valid probability.)
- If just one of $v$ or $w$ (say, $v$) is in $S$, then add $1$ to $v$'s tally with probability $\frac 3n$. If we do, then with probability $\frac{p}{3/n}$, let $e_i = vw$.
- If neither $v$ nor $w$ is in $S$, then just set $e_i = vw$ with probability $p$.
For each $v \in S$, the label on $v$ is at least the number of edges in $e_1, \dots, e_n$ incident on $v$, because whenever we select such an edge, we also increase the label of $v$. Also, the labels on the vertices in $S$ are independent, and with a relatively nice distribution: each label has $\sqrt n-1$ occasions on which it can increase with probability $\sqrt{\frac 3n}$, and $n-\sqrt n$ occasions on which it can increase with probability $\frac 3n$.
With probability $(1 - \sqrt{\frac 3n})^{\sqrt n -1} (1 - \frac 3n)^{n-\sqrt n}$, a vertex $v \in S$ never has its label increase. As $n \to \infty$, this probability tends to the rather awkward quantity $e^{-3-\sqrt 3} \approx 0.0088$. The labels on the vertices of $S$ are independent, so the probability that all vertices in $S$ have positive label is $(1 - e^{-3-\sqrt 3})^{\sqrt n}$.
This function is approximately $0.99^{\sqrt n}$, which is not quite the exponential in $n$ we wanted, but it is going to eventually go to $0$ much faster than $\frac1{n(n+1)}$. And if a vertex in $S$ has label $0$, then it is certainly not covered by the edges $e_1, \dots, e_n$, so we obtain the result we wanted.
Best Answer
Let $A_k = P($vertex k is adjacent to three edges with different colors$)$.The problem asks for $P(\bigcup A_k)$, which is, by symmetry $$4P(A_1) - 6P(A_1 \cap A_2) + 4P(A_1\cap A_2\cap A_3) - P(A_1\cap A_2\cap A_3\cap A_4)$$ And notice that $A_1\cap A_2\cap A_3 = A_1\cap A_2\cap A_3\cap A_4$