2026-314

Let \(A\) be the \(N \times N\) adjacency matrix of an undirected, unweighted network without self-loops. Let \( \textbf{1}\) be a column vector of \(N\) elements, all equal to 1, i.e., \( \textbf{1} = (1, 1, \ldots, 1)^T \). Let \(t(A)\) denote the trace of matrix \(A\), i.e., the sum of the elements on its main diagonal.

Which of the following expressions gives the number of connected triplets in the network?

1. \( ( \textbf{1}^T A^2 \textbf{1} ) / 2 \)
2. \( ( \textbf{1}^T A^2 \textbf{1} - t(A^2) ) / 2 \)
3. \( ( \textbf{1}^T A^2 \textbf{1} - t(A^2) - t(A^3) ) / 2 \)
4. \( ( \textbf{1}^T A^2 \textbf{1} - t(A^2) ) / 2 - t(A^3)/6 \)
5. None of the above

Original idea by: Pedro Ferreira