[Math] Can a graph with 7 vertices and 17 edges have an isolated vertex

discrete mathematicsgraph theory

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?

Best Answer

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?

Related Question