For each natural number $n \ge 5$ give a simple graph with $n$ vertices like $G$ so that: $\kappa(G) < \delta(G)\ ,\ \delta() = n−3$

61 Views Asked by At

For each natural number $n \ge 5$ give a simple graph with $n$ vertices like $G$ so that:

$\kappa(G) < \delta(G)\ ,\ \delta(G) = n−3$

$\kappa(G)$ is the minimum size of vertex cut and a vertex cut of a graph $G$ is a subset of vertices $V$ such that $G-{V}$ is disconnected.

1

There are 1 best solutions below

0
On

This is the most natural construction I can come up with. Here there are two disjoint copies of $K_2$ and one copy of $K_{n-4}$, and we add every possible edge between a $K_2$ and the $K_{n-4}$.

Graph with connectivity less than delta, where delta is n minus 3.