Maximum size of G

Printable View

January 6th 2012, 03:16 AM
alexmahone

Maximum size of G

Let $G$ be a graph of order $n$ that is not connected. What is the maximum size of $G$ ?
January 6th 2012, 03:41 AM
Plato

Re: Maximum size of G

Quote:

Originally Posted by alexmahone

Let $G$ be a graph of order $n$ that is not connected. What is the maximum size of $G$ ?

What is meant by "the size of G"?
January 6th 2012, 03:43 AM
alexmahone

Re: Maximum size of G

Quote:

Originally Posted by Plato

What is meant by "the size of G"?

the number of edges in G
January 6th 2012, 04:38 AM
Plato

Re: Maximum size of G

Quote:

Originally Posted by alexmahone

the number of edges in G

Here is a classic problem.
If $\|\mathcal{E}\|$ is the number of edges and $\|\mathcal{E}\|>\frac{(n-1)(n-2)}{2}$ prove the graph is connected.
January 6th 2012, 04:48 AM
alexmahone

Re: Maximum size of G

Quote:

Originally Posted by Plato

Here is a classic problem.
If $\|\mathcal{E}\|$ is the number of edges and $\|\mathcal{E}\|>\frac{(n-1)(n-2)}{2}$ prove the graph is connected.

The maximum number of edges in a graph of order $n-1$ is $\binom{n-1}{2}=\frac{(n-1)(n-2)}{2}$ . If we add another vertex, any new edge will have to join the new vertex to one of the original $n-1$ vertices and the graph becomes connected.

So, are you saying that the answer to my question in post #1 is $\binom{n-1}{2}$ ?

All times are GMT -8. The time now is 09:22 PM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.