Relation between k and k-1 edge connected graph

Question

Is every k connected graph is k-1 connected or the reverse? I always get confused. Can someone explain with the help of an example.

Answer 1

The answer is that it depends on your definition, and if you provide the definition you are using I can be more specific.

1. The definition on mathworld is that a graph is $k$-connected if for every set of $k-1$ vertices, removing those vertices doesn't disconnect it. In this case, if a graph is $k$-connected then it is also $\ell$-connected for all $\ell<k$. To see this, notice that if removing many vertices cannot disconnect the graph, then you have no hope of disconnecting the graph by removing fewer vertices.

2. The definition on wikipedia is that a graph is $k$-connected if $k$ is the smallest positive integer such that deleting $k$ vertices can disconnect the graph. Because of the use of the word "smallest," a $k$-connected graph is neither $(k-1)$-connected nor $(k+1)$-connected. Under this definition, a clique on $m$ vertices is considered to be $(m-1)$-connected

3. Another definition I have seen is that a graph is $k$-connected if there is a set of $k$ vertices such that removing them disconnects the graph. Under this definition, a graph that is $k$-connected is also $\ell$-connected for all $\ell > k$ since we can choose the $\ell$ vertices by first picking the $k$ vertices known to disconnect the graph, and then picking the remaining $\ell-k$ vertices arbitrarily.

Definition $1$ and $3$ come at the problem from "different sides" in some sense, and definition $2$ is equivalent to requiring that both definition $1$ and $3$ hold.