1
$\begingroup$

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)

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

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:

enter image description here

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

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.