(definition)

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

**See also**
*biconnected graph*, *triconnected graph*, *cut vertex*.

*Note:
Informally, there are at least k independent paths from any vertex to any other vertex.*

Author: PMS

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 3 September 2019.

HTML page formatted Fri Sep 6 15:26:10 2019.

Cite this as:

Paul M. Sant, "k-connected graph", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 3 September 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/kconnectedGraph.html