connectivity of octahedron We can easily prove that the edge-connectivity is $\le4$ so then the connectivity of the octahedron is $\le4$ . It is obvious that there are not cut-vertices in the graph so that leaves either the connectivity to be either 2,3,4. I am trying to get a contradiction after assuming the connectivity is less than 4 but I cannot make sense of it. Can anyone point me in the right direction? ![enter image description here](

The octahedron is a symmetric graph. If we can find 4 independent paths between a vertex and one of its neighbors, and again between a vertex and the one other vertex which is not its neighbor, then the graph is 4-connected.

This is relatively straightforward for the neighbor; you have the direct path, the 2-length path to each side and the 3-length path through the opposite node.

The 4 paths to the opposite node are all length-2 through each adjacent node.

Therefore the octahedron graph is 4-connected.