k-connected graphs Explanation

Question

Can someone explain what a k-connected graph means with an example?

So I made a "triangle graph", like the one below, does that mean that the graph below is 1-connected, since that is the maximum number of vertices you can take out to make a connected graph?

Answer 1

A connected graph is $k$-connected if either after removing any $k - 1$ vertices the remaining graph is connected. The connectivity of a graph $G$ is the largest $k$ less than $n$ for which $G$ is $k$-connected.

Your example is 2-connected since removing any two vertices leaves a single vertex, which is a connected graph.

Here are some more examples:

• A tree with at least 2 vertices has connectivity 1.
• A graph with an articulation point has connectivity 1.
• A cycle has connectivity 2.
• The wheel graph (a cycle joined to a single vertex) has connectivity 3.
• The complete graph on $n$ vertices has connectivity $n-1$.