Program to count the number of edges in an undirected graph is discussed here. Given an adjacency list representation of an undirected graph, the task is to find the number of edges in it.
Algorithm to count the number of edges in an undirected graph
- Input the adjacency list representation of an undirected graph.
- In every finite undirected graph, the number of vertices with an odd degree is always even.
- Handshaking lemma is a consequence of the degree sum formula,
- So we traverse all vertices, compute the sum of sizes of their adjacency lists, and finally return sum/2.
Program to count the number of edges in an undirected graph is given below.
/* C++ program to count the number of edges in an undirected graph */
using namespace std;
/* Graph class declaration with vertex and edges */
int V ; // Vertex
list *adj; // Pointer for the edges
this->V = V ;
adj = new list[V]; // Add to the list
void add_edge_graph(int u, int v) ; // Function to add edges in a graph
int count_edges_graph() ; // Function to count the edges
/* Function to add edges in a graph */
void Graph :: add_edge_graph(int u, int v)
/* Function to count the edges */
int Graph :: count_edges_graph()
int sum = 0;
for (int i = 0 ; i < V ; i++)
sum += adj[i].size();
The count of edge is always even because in
undirected graph every edge is connected
twice between two vertices */
/* Main Function */
int V = 9 ;
int u, v;
cout << “\nEnter the connections of the nodes in the graph \n”;
cin >> u >> v;
cin >> choice; // Enter the choice, to continue, enter y or Y
g.add_edge_graph(u, v); /* Enter the vertex connection */
}while(choice == ‘y’ || choice == ‘Y’); /* If you want to continue */
cout << “\nTotal number of edges : ” << g.count_edges_graph() << endl;