2
$\begingroup$

QUESTION

Show a simple, no loop, 3 connected graph for which $\min(\deg(v))> \text { edge connectivity } > \text {vertex- connectivity}$.

Attempt

I tried going from a wheel (which are 3 connected) and adding some random vertices and edges all around but I couldn't get it to work. Then I started with some different complete graphs, which didn't help either.

Could you give me some tips on how to construct a graph of this type? More generally, what if the question asks for a $n$-connected graph?

$\endgroup$
1
$\begingroup$

I think the following works:

with minimum degree $5$, edge connectivity $4$ and vertex connectivity $3$.

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, unfortunately the graph must be 3-connected aswell. (Could you tell me what software you used to make that neat picture?) $\endgroup$ – YoTengoUnLCD Sep 16 '15 at 23:33
  • $\begingroup$ Oh, my bad. I made it with geogebra. $\endgroup$ – Jorge Fernández Hidalgo Sep 16 '15 at 23:33
  • $\begingroup$ I think this graph works. Please double check though. $\endgroup$ – Jorge Fernández Hidalgo Sep 17 '15 at 0:23
  • $\begingroup$ Holy damn, I'm almost sure it works! How'd you come up with that? Thank you a lot!! $\endgroup$ – YoTengoUnLCD Sep 17 '15 at 0:29
  • $\begingroup$ I started by placing the three vertices that where going to form the cut-set and then I tried a lot of stuff. $\endgroup$ – Jorge Fernández Hidalgo Sep 17 '15 at 0:33

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.