The question is Calculate the maximum number of edges in a simple graph with nnodes and k components.

I dont really understand what the question means .. and how to solve this..

Thanks...

Printable View

- Dec 6th 2012, 07:42 AMkakatomyQuestion about graph
The question is Calculate the maximum number of edges in a simple graph with nnodes and k components.

I dont really understand what the question means .. and how to solve this..

Thanks...

- Dec 6th 2012, 08:32 AMPlatoRe: Question about graph
A

*component*is a maximally connected subgraph of a graph.

You need to check your text material. Some authors allow degenerate components, one vertex, most do not.

Here is an example: Consider a twelve vertex graph with three components having three, four and five vertices.

Then the graph could be $\displaystyle K_3\cup K_4\cup K_5$.

That is a maximum of $\displaystyle 3+6+10=19$ edges in all.

That said, I don't know how to solve the general case. - Dec 6th 2012, 09:03 AMkakatomyRe: Question about graph