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$
4
  • $\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, 2014 at 16:47
  • 1
    $\begingroup$ Please add that to the question directly, instead of just being a comment. $\endgroup$
    – Calvin Lin
    Feb 26, 2014 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, 2014 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, 2014 at 17:16

1 Answer 1

Reset to default
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$

$\endgroup$
4
  • $\begingroup$ How did you make those nice graphs? They don't look like mathematica's style. $\endgroup$
    – Ragnar
    Feb 26, 2014 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, 2014 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, 2014 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, 2014 at 17:59

You must log in to answer this question.

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