# Vertex and edge connectivity of a graph

I want to draw a graph of 8 vertices and 16 edges with maximum vertex connectivity and maximum edge connectivity and also draw a graph with minimum vertex connectivity and minimum edge connectivity .but l have no idea, please help.(i means that i want to two different graph but both are 16 edges and 8 vertices)

• You can't get all four of those at once! – Henning Makholm Oct 23 '16 at 18:20

## 1 Answer

The example with minimum connectivity is trivial, just take a disconnected graph with $8$ vertices and $16$ edges, to do this take a copy of $K_7$ and an isolated vertex, and remove any $3$ edges you want.

To get the example with maximum connectivity first notice that the average degree is $4$, so the maximum edge-connectivity is at most $3$, and consequently the maximum vertex connectivity is also at most $3$.

The following graph reaches these connectivities: • Tell me if you have trouble proving the graph in fact reaches those connectivities. – Jorge Fernández Hidalgo Oct 23 '16 at 19:03