Independence Number Calculator
Find the maximum independent set - a set of vertices with no edges between them.
Graph Input
Maximum Independent Set
{v0, v2}
These vertices form an independent set (no edges between them).
Vertex Degrees
v0
2
v1
2
v2
2
v3
2
v4
2
Independence Number
alpha(G) = 2
Vertices
5
Edges
5
Vertex Cover Size
3
Turan Bound
1
Bounds
Caro-Wei Lower Bound1.6667
Turan Lower Bound1
alpha + tau (vertex cover)= 5
About Independence Number
- An independent set has no edges between its vertices
- alpha(G) is the size of the maximum independent set
- alpha(G) + tau(G) = n (vertex cover complement)
- Computing alpha(G) is NP-hard