# Thread: Is there such a graph?

1. ## Is there such a graph?

Is there a graph that is 1-connected and 3-connected, but not 4-connected? Why?

First off, can someone give the definition of being 1,3,or 4 connected in 'English'. All the def. are so technical and I don't really understand.

2. Originally Posted by jzellt
Is there a graph that is 1-connected and 3-connected, but not 4-connected? Why?

First off, can someone give the definition of being 1,3,or 4 connected in 'English'. All the def. are so technical and I don't really understand.
Intuitively a graph $G=\left(V,E\right)$ is, say $2-connected$ (i.e. biconnected) if it has no, what is called "articulation points". These are points for which you can take away and leave the graph disconnected. In other words, no matter what vertex you take away from $G$ it remains connected. Think of this as a network flow having redundancies. If a server goes down there are other serves which still connect all the mainframes, and thus everything stays connected.

3. So let me make sure I understand you correctly. Say G is 3 connected. This means I can pick and remove and 2 vertices and G will remain connected. But If I remove 3, then G will be disconnected. Correct?

4. Originally Posted by jzellt
So let me make sure I understand you correctly. Say G is 3 connected. This means I can pick and remove and 2 vertices and G will remain connected. But If I remove 3, then G will be disconnected. Correct?
Eh....it means that no matter which two vertices you remove the resulting graph will be connected. It says nothing about three vertices.

5. So, does the complete graph on 4 vertices meet my requirements? I can remove 1 vertex - still connected. I can remove 3 vertices - still connected. But If I remove 4 vertices, then I have no more graph...

6. I'm pretty sure that the graph I described above works. Are there others? Thanks.