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

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

Printable View

- Oct 18th 2007, 07: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. - Oct 18th 2007, 09: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. - Oct 18th 2007, 07:50 PMle_su14