CODEWITHSUNDEEP
graphtheory
user8451797
user8451797

Reputation: 63

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

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

Upvotes: 4

Views: 3569

Answers (1)

senderle
senderle

Reputation: 151067

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.

Upvotes: 6

Related Questions