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?

  • $\begingroup$ What makes you think $\kappa'(G)=2$? $\endgroup$ – bof Mar 25 '18 at 21:43
  • $\begingroup$ 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 $\endgroup$ – Zainab Husain Mar 25 '18 at 21:43
  • $\begingroup$ The edge-connectivity of G, written κ′(G) is the minimum size of a disconnecting set. <- definition from my professor. $\endgroup$ – Zainab Husain Mar 25 '18 at 21:50
  • 1
    $\begingroup$ 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. $\endgroup$ – bof Mar 25 '18 at 22:10
  • 1
    $\begingroup$ 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.$ $\endgroup$ – bof Mar 25 '18 at 22:22

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$


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.