1
$\begingroup$

How can i construct a graph $G$ with these properties:

  • $G$ is $4$-edge-connected;
  • $G$ is $2$-vertex-connected;
  • $G$ is not $3$-vertex-connected.

I have managed to create a number of $4$-edge-connected graphs but they always turn out to be $3$-vertex connected - which I can't have.

essentially, i have used trial and error thus far to construct some 4-edge-connected graphs but i'm struggling to see how i can do this without the resulting graphs also being 3-connected.

4-edge connected meaning a graph in which between any two vertices there are 4 edge-disjoint paths between the two vertices. 2-connected(meaning 2 vertex-connected) means a graph in which between any two vertices there are 2 vertex-disjoint paths.

It's a homework question for a module and could easily be a part of the final year exam - The question explicitly asks for a graph with these three properties, and then to prove that it has these properties.

$\endgroup$
  • $\begingroup$ 4-edge connected meaning a graph in which between any two vertices there are 4 edge-disjoint paths between the two vertices. 2-connected(meaning 2 vertex-connected) means a graph in which between any two vertices there are 2 vertex-disjoint paths. $\endgroup$ – user3355894 Feb 26 '14 at 16:47
  • 1
    $\begingroup$ Please add that to the question directly, instead of just being a comment. $\endgroup$ – Calvin Lin Feb 26 '14 at 16:48
  • $\begingroup$ @user3355894 as well adding the comment to the question, could you give some idea of why you think this should exist, and what you have already tried e.g. how you are making these 4 edge connected graphs that turn out to be three vertex connected $\endgroup$ – Joe Tait Feb 26 '14 at 17:01
  • $\begingroup$ Take two of the 4-edge-connected graph and attache them at two vertices you get a 2-connected graph. $\endgroup$ – hbm Feb 26 '14 at 17:16
2
$\begingroup$

What about such a graph:

$\hspace{50pt}$example

You could easily also make it 3-vertex connected, but not 4-vertex connected in the same way, etc.

$\hspace{50pt}$example

I hope this helps $\ddot\smile$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How did you make those nice graphs? They don't look like mathematica's style. $\endgroup$ – Ragnar Feb 26 '14 at 17:21
  • $\begingroup$ @Ragnar Thank you, I use inkscape. If you are wondering if it is good for you, there are also some other, even nicer diagrams. $\endgroup$ – dtldarek Feb 26 '14 at 17:40
  • $\begingroup$ Thanks for your help here, but i'm not sure about this graph because i can quickly find two vertices for which there are at least 3 vertex disjoint paths between them... this would make the graph 3 vertex connected would it not? I am referring to the first graph which you say is not 3 vertex connected $\endgroup$ – user3355894 Feb 26 '14 at 17:56
  • $\begingroup$ @user3355894 If you remove the two middle vertices, then the graph becomes disconnected, and so it is not 3-vertex connected. $\endgroup$ – dtldarek Feb 26 '14 at 17:59

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.