# Maximum size of G

• Jan 6th 2012, 03:16 AM
alexmahone
Maximum size of G
Let $\displaystyle G$ be a graph of order $\displaystyle n$ that is not connected. What is the maximum size of $\displaystyle G$?
• Jan 6th 2012, 03:41 AM
Plato
Re: Maximum size of G
Quote:

Originally Posted by alexmahone
Let $\displaystyle G$ be a graph of order $\displaystyle n$ that is not connected. What is the maximum size of $\displaystyle G$?

What is meant by "the size of G"?
• Jan 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
• Jan 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 $\displaystyle \|\mathcal{E}\|$ is the number of edges and $\displaystyle \|\mathcal{E}\|>\frac{(n-1)(n-2)}{2}$ prove the graph is connected.
• Jan 6th 2012, 04:48 AM
alexmahone
Re: Maximum size of G
Quote:

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

The maximum number of edges in a graph of order $\displaystyle n-1$ is $\displaystyle \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 $\displaystyle n-1$ vertices and the graph becomes connected.

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