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.
Best Answer
What about such a graph:
$\hspace{50pt}$
You could easily also make it 3-vertex connected, but not 4-vertex connected in the same way, etc.
$\hspace{50pt}$
I hope this helps $\ddot\smile$