I am not sure about this question

[Ishaan Joshi]

How does one go about answering it ?

Q :

 Consider the collection of all graphs with  10 nodes and 6 edges. Let M and m be, respectively, the maximum and minimum number of connected components in each member of this collection. If the graph has no self loops and there is at most one edge between any pair of nodes, which one of the following is true :

A) M = 10, m = 10
B) M = 10, m = 1
C) M = 7, m = 4
D) M = 6, m = 4
E) M = 6, m = 3

Would appreciate any answers !

cheers,


..i[j]
--
What is freedom of expression? Without the freedom to offend, it ceases to exist. - Salman Rushdie

[Arun]

I may be wrong, but I think the answer is D.

A connected component is a basically a connected subgraph (i.e. there
is a path from every node to every other node).

To get minimum: connect 7 nodes with 6 edges. This will be 1
component. There are 3 remaining disconnected nodes without an edges
to or from them, which are considered components. 3+1=4

To get maximum: Take the first 3 nodes and connect them with three
edges. This is one component. Take the next 3 nodes and do the
same. This is another connected component. The 4 remaining nodes
make up 4 separate connected components. So, 1+ 1+ 4 = 6.

This is assuming a lone vertex without any edges to or from it is
considered a connected component.

Correct me if I'm wrong.

- Arun

[habiba]

My answer is C.  M= 7 and m = 4

for m = 4  my reasoning is almost the same as Arun, instead of connecting 7 vertices with wit 6 edges, i started of with 1 edge between each pair of vertices so for 10 there are 5 pairs and 1 edges used , 1 left which can be used to join any 2 of the  5 components so in the end we get 4 component.

Now, for M= 7.

The way i was going about it is create a clique... so 4 vertices will use up the 6 edges, hence 6 isolated vertices (each an independent component) + 1 component( of  size 4 ) = 7 components.

 

On 4/6/07, Arun <perso...@gmail.com> wrote:

I may be wrong, but I think the answer is D.

A connected component is a basically a connected subgraph ( i.e. there

[Arun]

Yeah, this is right. My mistake. Thanks. Answer is C using same
logic.

On Apr 6, 8:26 pm, habiba <habi...@gmail.com> wrote:
> My answer is C. M= 7 and m = 4
> for m = 4 my reasoning is almost the same as Arun, instead of connecting 7
> vertices with wit 6 edges, i started of with 1 edge between each pair of
> vertices so for 10 there are 5 pairs and 1 edges used , 1 left which can be
> used to join any 2 of the 5 components so in the end we get 4 component.
> Now, for M= 7.
> The way i was going about it is create a clique... so 4 vertices will use up
> the 6 edges, hence 6 isolated vertices (each an independent component) + 1
> component( of size 4 ) = 7 components.
>

> On 4/6/07, Arun <personx...@gmail.com> wrote:
>
>
>
> > I may be wrong, but I think the answer is D.
>

> > A connected component is a basically a connected subgraph (i.e. there