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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.