# What is κ(G) and κ′(G) and δ(G) for graph G?

Am I correct to say that G is 4-connected?

So κ(G) = 4 but then κ′(G)=2 but that cannot happen since κ(G)<=κ′(G)<=δ(G)

I know δ(G)=4 so wouldn't κ′(G)=4 then? However, I don't see how that would happen.

• What makes you think $\kappa'(G)=2$? – bof Mar 25 '18 at 21:43
• Sorry, I corrected it. I meant κ(G) =4. I'm thinking that the 4 middle vertices that are on the horizontal axis are the set of cut vertices, and if those are removed the graph disconnects into 2 parts making κ′(G)=2 – Zainab Husain Mar 25 '18 at 21:43
• The edge-connectivity of G, written κ′(G) is the minimum size of a disconnecting set. <- definition from my professor. – Zainab Husain Mar 25 '18 at 21:50
• You mean "a disconnecting set" of edges, right? Do you see a way to disconnect your graph by removing $2$ (or $3$ edges? I don't. – bof Mar 25 '18 at 22:10
• If you don't see a way to disconnect the graph by removing two edges, then it is a mystery to me why you say that $\kappa'(G)=2.$ – bof Mar 25 '18 at 22:22

Vertex Connectivity: $\kappa(G)$ is the minimum size of a vertex set S s.t. G\S is disconnected.
Edge Connectivity: $\lambda(G)$ or $\kappa'(G)$ is the minimum size of edge set F s.t. G\F has more than one component.
in your graph $\kappa(G)=4$: for example $S=\{f,l,i,c\}$ and
$\lambda(G)=4$ for example $F=\{\{f,e\},\{l,k\},\{i,g\},\{c,d\}\}$
$\kappa(G)\le\lambda(G)\le\delta(G)$ (Whitney 1932, Harary 1994):
for your graph $\kappa(G)=\lambda(G)=\delta(G)=4$