The sum the adjacency matrix

Task number: 3915

Let \(G\) be a graph and \(A = (a_{ij})_{i,j=1}^n\) its adjency matrix. Determine the sum of elemenets of \(A\), as a function of the number of vertices and edges, i.e. an expression \( \sum\limits_{i,j=1}^n a_{ij}. \)
  • Hint

    What is the sum of one row?
  • Solution

    The sum of one row is equal to the degree of the corresponding vertex.

    In the grand total, each edge is counted twice.

  • Answer

    The sum of the matrix is \(2|E|\).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email