To address Problem 1 and solve it rigorously, let us break it down into parts.

Complete Graph $K_p$:

• A complete graph $K_p$ has $p$ vertices, and every vertex is connected to every other vertex.

Adjacency Matrix of $K_p$:

• The adjacency matrix $A$ of $K_p$ is: \begin{cases} 1 & \text{if } i \neq j, \\ 0 & \text{if } i = j. \end{cases}$$

Part (a): Paths of Length $n$ from a Vertex to Itself

The number of paths of length $n$ from a vertex to itself corresponds to the diagonal entries of $A^n$, the $n$-th power of the adjacency matrix $A$. Since all vertices in $K_p$ are symmetric, the calculation for any vertex suffices.

1. Diagonal Entry Formula:
   • The adjacency matrix $A$ has $p-1$ off-diagonal ones for each row, and zeroes on the diagonal.
   • For paths of length $n$, the diagonal entry counts paths that start and return to the same vertex. This involves choosing $n-1$ intermediate vertices such that no two consecutive vertices are the same. There are $(p-1)$ choices for each of these steps.
   • Hence, the number of such paths is: $(p-1)^n.$

Part (b): Paths of Length $n$ from a Vertex to a Different Vertex

Here, we count paths of length $n$ starting at one vertex and ending at another.

1. Non-Diagonal Entries:
   • A path begins at a specific vertex and must end at a different vertex. For the first step, there are $(p-1)$ choices of vertices. For each of the remaining $n-1$ steps, there are $(p-1)$ choices of vertices since no vertex can be revisited consecutively.
   • Therefore, the number of such paths is: $(p-1)^{n-1}.$

Concluding Formula for Sequences $a_1 a_2 \cdots a_n$:

To satisfy the constraints $a_i \neq a_{i+1}$ for $i \in [n-1]$, and $a_n \neq a_1$, we proceed as follows:

• The first vertex has $p$ choices.
• The second vertex has $(p-1)$ choices (to avoid repetition of the first).
• For the $n-2$ intermediate steps, each vertex has $(p-1)$ choices.
• For the last vertex $a_n$, there are $(p-2)$ choices, as it must be distinct from both $a_{n-1}$ and $a_1$.
• The total number of sequences is therefore: $p \cdot (p-1)^{n-2} \cdot (p-2).$

Summary:

1. Paths of Length $n$ from a Vertex to Itself: $(p-1)^n$
2. Paths of Length $n$ from a Vertex to a Different Vertex: $(p-1)^{n-1}$
3. Formula for Sequences $a_1, a_2, \ldots, a_n$ with Constraints: $p \cdot (p-1)^{n-2} \cdot (p-2).$

Would you like further clarification, or shall I expand on a specific aspect?

Related Questions:

1. What changes if $K_p$ is directed instead of undirected?
2. How do the eigenvalues of the adjacency matrix influence these path counts?
3. What happens when $n$ is small, such as $n = 1$ or $n = 2$?
4. Can this be generalized to graphs other than complete graphs?
5. How does the count change if diagonal entries of $A$ are set to 1 (i.e., self-loops are allowed)?

Tip:

Matrix exponentiation techniques can efficiently compute $A^n$ for large $n$, saving computational effort.