Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why do self loop counts twice when finding the degree of a vertex?

Tags:

graph

theory

In a undirected graph, a self-loop adds two to the node's degree. Why doesn't it just add one?

like image 346
user8451797 Avatar asked Oct 22 '25 05:10

user8451797


1 Answers

Consider a graph without self-loops. Suppose you can't see it, but you're told the degree of every node. Can you recreate it?

In many cases the answer is "no," because the degree contains no information about which node a particular edge connects to.

So the real question is this: should we pay attention to which node a self-loop connects to, even though we don't pay attention for any other kind of edge?

From that perspective, I think it's clear that to be consistent, we must consider self-loops as adding two to the node's degree.

Another way of putting this would be to point out that in a graph without self-loops, the number of edges is exactly half the sum of the degrees of all the nodes. Should that really change if the graph has self-loops? Again, I think it's clear that the answer is no.

like image 70
senderle Avatar answered Oct 26 '25 00:10

senderle



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!