'An undirected graph having n edges, then find out no. of vertices that graph have?
An undirected graph having 'n' number of edges, then find out number of vertices that graph have?
Solution 1:[1]
Since an edge is a connection between to vertices, the amount of vertices is at max 2n.
The amount of vertices is at minimum n+1. (This is pretty logical if you imagine that you have 2 edges - then you will at minimum have 3 vertices, because each edge must connect 2 vertices)
So if e = n, then n+1 <= v <= 2n
Solution 2:[2]
There is no exact formula for the number of vertices in terms of number of edges in the general case. However, if you take special cases, you can say more: if the graph is a tree, then the number of vertices is one more than the number of edges.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Zebraboard |
| Solution 2 | Ashwin Ganesan |