[Math] Finding Euler path using powers of adjacency

adjacency matrixdiscrete mathematicseulerian-pathgraph theory

Context: I'm studying an introductory course to Discrete Applied Mathematics, and am new to the context of graphs.

Knowing that a graph can be represented as an adjacency matrix, say we have the graph

$G = \begin{bmatrix}
0 & 1 & 0 & 1 & 0 & 0\\
1 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1\\
1 & 1 & 1 & 0 & 0 & 1\\
0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0\\
\end{bmatrix}$

I know we can look at $G^n$ to find the number of paths which connect any two vertexes given by $n$ walked paths. Trying to use $G^{vertexes}$, I thought I could check how many possible solutions for an Euler circuit there were based on the initially chosen vertex.

I quickly noticed that there was a flaw in my thinking: this allowed both paths and vertexes to be repeated on the path, which is not allowed in the definition of an Eulerian cycle.

I know I can see if an Eulerian cycle exists counting the number of vertexes in the graph having odd and even edges joining other vertexes.

  • If all vertexes have an even number, or exactly two uneven, of connected lines, there must exist at least one Eulerian cycle.
  • If there is exactly one, or more than two uneven vertexes, the Eulerian cycle doesn't exist.

This tells me nothing about where the starting position must be (unless there are two uneven ones), or the trajectory of the path.

Is there any property I can use to limit the amount of repetitions of paths/vertexes, using the exponentiation technique, in order to see what starting position are valid? Are there any other thing I should know about Eulerian circuits?

Best Answer

My comment above with Markov chain probability matrices was a bit hasted and only gave me exact number in some special cases.

I will instead present a more exact algorithm for you.

We will need a couple of building blocks:

  1. Adjacency matrix $\bf M$ of dimension $N\times N$.
  2. Matrix multiplication.
  3. Hadamard/Schur (elementwise) product $(\otimes)$.
  4. A specific circuit-remover matrix ${\bf O}={\bf 1 1} ^T{\bf - I}$, Where $\bf 1$ is the column vector of $N$ ones.

($\bf O$ is basically a logically inverted unit matrix, $0$ on diagonal and $1$ everywhere else)

Now define the matrix : $$\cases{{\bf T}_0 = {\bf M}\\{\bf T}_{k+1} = {\bf M}({\bf O \otimes T}_k)}$$

Then calculate the sum $${\bf s}=\sum_{k=0}^{N-1} \text{diag}({\bf T}_k)$$

Where diag is the operator that makes a vector from the diagonal elements. For example $$\text{diag}\left(\begin{bmatrix}1&2&13\\2&3&4\\13&4&5\end{bmatrix}\right) = [1,3,5]^T$$

You can note that if $\bf O$ was matrix filled with ones then ${\bf T}_k = {\bf M}^{k-1}$ (ordinary iterated matrix multiplication "power") which is what you realized could not be the case. So we only needed do a quite minor modification to your first idea.

I almost forgot to mention, the $\bf s$ vector will be a vector containing integers how many paths from position back to same position passing any node on the way maximally 1 time.

Related Question