CODEWITHSUNDEEP
algorithmgraph
Arat254
Arat254

Reputation: 469

For a graph, given that a vertex has a loop, why is the degree of that vertex taken as 2 instead of 1?

I was reading a book called "Discrete Mathematics and Its Applications" by Kenneth H. Rosen. In the book, the degree of a vertex of an undirected graph is defined as follows:

"The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by deg(v)."

I am a bit confused as to why the degree of the vertex if there is a loop is taken as 2 instead of 1. What is the reason for this? If we want to keep track of the number of edges in the graph shouldn't we take it as 1 instead of 2?

Upvotes: 0

Views: 471

Answers (1)

tucuxi
tucuxi

Reputation: 17945

This has very little to do with programming, and a lot to do with math (some would say that the distinction between both is somewhat arbitrary).

My take is that it is simpler to define it this way, and more consistent in the general case of directed graphs. Imagine you have a directed graph data-structure, with incoming and outgoing edges:

struct Node {
   int id;
   vector<Edge> outgoing;
   vector<Edge> incoming;
}

With the definition in the book, 

int degree(const Node &node) {
  return outgoing.size() + incoming.size();
}

With the alternative definition (not counting loops twice), you would need to make a special case for edges that are both incoming and outgoing.

Upvotes: 1

Related Questions