# Can a graph with 7 vertices and 17 edges have an isolated vertex?

The question is:

Show or disprove that a graph with 7 vertices and 17 edges can have an isolated vertex.

I know what is an isolated vertex, but don't know how to connect it with the concrete question. Any hints?

• How many edges can a graph with 6 vertices have? Jun 12 '13 at 18:29

If you allow loops and/or multiple edges between vertices, then such a graph exists. Take $1$ vertex with $17$ loops, or two vertices with $17$ edges between them, and let the other vertices be isolated.

Now assuming we are working with a simple graph (no loops, and no multiple edges), then no such graph exists. This is because the maximum number of edges that can exist on a simple graph of $6$ vertices is $15$. Can you see why?

I assume your graph can't have parallel edges or loops, otherwise statement is true since you can connect two arbitrary vertices with all the 17 edges and 5 vertices left are isolated.

So in this case the maximum number of edges in undirected graph of n vertices is ${n \choose 2}$ (number of pairs of vertices). For $n=6$ maximal number of edges is 15, so if you add a vertice to them, there are at least 2 edges ($17-15$) that cover this vertice, so no vertice is isolated.

The following graph is a simple 7-vertex graph with an isolated vertex. It contains every possible edge subject to the constraint that it has an isolated vertex.

Any other 7-vertex graph with an isolated vertex would consequently be a subgraph of this graph, thus is cannot have more edges.

The graph above has $\binom{6}{2}=15 < 17$ edges, so a $17$-edge $7$-vertex simple graph with an isolated vertex cannot exist.