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

Printable View

- Jan 6th 2012, 03:16 AMalexmahoneMaximum 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 AMPlatoRe: Maximum size of G
- Jan 6th 2012, 03:43 AMalexmahoneRe: Maximum size of G
- Jan 6th 2012, 04:38 AMPlatoRe: Maximum size of G
- Jan 6th 2012, 04:48 AMalexmahoneRe: Maximum size of G
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}$?