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 Answer 1

1
$\begingroup$

I think the following works:

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

enter image description here

$\endgroup$
6
  • $\begingroup$ Thanks, unfortunately the graph must be 3-connected aswell. (Could you tell me what software you used to make that neat picture?) $\endgroup$ Sep 16, 2015 at 23:33
  • $\begingroup$ Oh, my bad. I made it with geogebra. $\endgroup$
    – Asinomás
    Sep 16, 2015 at 23:33
  • $\begingroup$ I think this graph works. Please double check though. $\endgroup$
    – Asinomás
    Sep 17, 2015 at 0:23
  • $\begingroup$ Holy damn, I'm almost sure it works! How'd you come up with that? Thank you a lot!! $\endgroup$ Sep 17, 2015 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$
    – Asinomás
    Sep 17, 2015 at 0:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .