This is possibly simple, but I'd like to check my reasoning because it seems "too simple".

Consider an undirected graph of $N$ nodes.

We set it up so that each node is connected to a fixed number of other nodes, i.e. every node has the same degree, $k$.

I'd like to know how many edges there are in the graph. It would be fewer than $kN$, because one of node A's edges say $\overline{AB}$ would also count as one of B's edges.

The way I approached the problem was to consider the adjacency matrix $A$. As the graph is unweighted, each row of the matrix would have $k$ ones in it. So the sum of all elements in $A$ would be $kN$.

As the graph is undirected, the matrix is symmetric and all of the relevant information about the edges is in the upper diagonal of $A$.

The graph contains no self-loops so $\text{tr}(A) = 0$.

Therefore, the total number of unique edges should be $1/2$ the sum of the whole matrix $A$, or:

$$\text{number of edges} = \frac{kN}{2} $$

Does this seem right? Or am I missing something in my logic. I am new to graph theory. I've not seen this problem addressed anywhere only, which makes me think it's either too complicated or trivial.



Yes, your are right. A standard double-counting argument (of the number of pairs $(v,e)$ where a vertex $v$ is incident to an edge $e$) shows that the sum of degrees of the veritces of $G$ is twice the number of its edges.


Your Answer

