1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ How many edges can a graph with 6 vertices have? $\endgroup$ – Hagen von Eitzen Jun 12 '13 at 18:29
2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

A 7 vertex graph with 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.