Why make a (single) loop correspond to an entry of 1 in the adjacency matrix of an undirected graph?

Question

There seems to be two conventions for how to write the adjacency matrix of an undirected graph containing a loop. One convention is to have the loop contribute 2 to the corresponding entry in the adjacency matrix. This has the nice effect of still being consistent with the degree of a vertex simply being the corresponding row or column sum. There is another convention though to have the loop contribute 1 to the corresponding entry in the adjacency matrix. I was wondering if there are any particular justifications for this choice i.e. properties of the adjacency matrix that this allows for.

Answer 1

I assume that anyone who takes the convention that loops are written as $1$ in the adjacency matrix also takes the convention that loops contribute $1$ to the degree of a vertex. This has both advantages and drawbacks:

• You want a loop to contribute $1$ to the degree so that the degree of a vertex (the sum of a row in the adjacency matrix) is the number of incident edges;
• You want a loop to contribute $2$ to the degree so that the total degree of all vertices (the sum of all entries in the adjacency matrix) is twice the total number of edges.

If $A$ is the adjacency matrix, then the $(i,j)^{\text{th}}$ entry of $A^n$ counts the number of length-$n$ paths from $i$ to $j$. In the context of this application, I'd probably want loops to be represented by a $1$. Putting a $2$ in the $(i,i)^\text{th}$ entry of $A$ to indicate a loop would introduce a factor of $2$ in paths through $i$ that take that loop: essentially, they can take the edge "forward from $i$ to $i$" or "backward from $i$ to $i$". I'm sure this makes sense sometimes, but by default I wouldn't want this behavior.

(For example, if $G$ is the graph on two vertices $\{0,1\}$ with an edge between $0$ and $1$ and a loop at $0$, paths in $G$ should correspond to binary strings with no two consecutive $1$'s, which are enumerated by the Fibonacci numbers. Powers of the adjacency matrix of $G$ only reflect this if the loop at $0$ corresponds to a $1$ in the adjacency matrix.)