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

3.6k Views Asked by At

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.

Could someone please explain this?

1

There are 1 best solutions below

0
On

I hope it can help you
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.

enter image description here

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$