Na teoria dos grafos, um grafo G é dito k-vértice-conexo (ou k-conexo) se tem mais de k vértices e permanece conexo sempre que são removidos k-1 vértices.