G = (V,E) has v vertices, e edges and p connected components.

Prove that e = (v - p)(v - p + 1)/2.

Printable View

- October 18th 2007, 06:25 AMle_su14Connected components.
G = (V,E) has v vertices, e edges and p connected components.

Prove that e = (v - p)(v - p + 1)/2. - October 18th 2007, 08:44 AMPlato
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. - October 18th 2007, 06:50 PMle_su14