Use Excercise 35 to show that a simple graph with $n$ vertices and $k$ connected components has at most MATH edges.

Solution:

Excercise 35 proved that a simple connected graph has

MATH

edges.

A simple graph with $n$ vertices and $k$ connected components has at least $k$ vertices, ie $n\geq k$.

The amount of edges in such a graph are maximized when a single component has the maximum amount of vertices and still satisfies $n\geq k$.

In this case, every component will have only one vertex, except one, which has all of the other vertices.

All components except one will have no edges.

The other component will have MATHvertices.

If we put this into the formula from #35, we have MATHedges.

This document created by Scientific Notebook 4.0.