A connected graph such that deleting any k-1 vertices (and incident edges) results in a graph that is still connected.