Exercise 1.1.3

These are the solutions to the exercises of the book Graph Theory with Applications by J. A. Bondy and U. S. R. Murty.

If GG is simple, then at most, GG  could have an edge between every two distinct vertices. The total number of possible combinations are (ν2)\binom{\nu}{2} (there are (ν2)\binom{\nu}{2} ways of choosing 2 distinct vertices from a set of ν\nu vertices). Hence ϵ(ν2)\epsilon\leq \binom{\nu}{2}. \square

The solutions of all the exercises of “Graph Theory with Applications” by J. A. Bondy and U. S. R. Murty, are available for download as a pdf file! Click the button below.