Thread: Connected components.

G = (V,E) has v vertices, e edges and p connected components.
Prove that e = (v - p)(v - p + 1)/2.

There is something wrong with the formula you posted.
Look at the attached graph. It has 2 components, 7 vertices, and 7 edges.
Even if it were about maximal components there will be only two more edges in this graph. The formula still does not work.

Originally Posted by Plato

There is something wrong with the formula you posted.
Look at the attached graph. It has 2 components, 7 vertices, and 7 edges.
Even if it were about maximal components there will be only two more edges in this graph. The formula still does not work.

Oh, I'm sorry!
The true fromula is e <= (v - p)(v - p + 1)/2