So I'm reading about k-connected graphs, and I'm a little confused about them. This is the main definition I've seen:

A graph is k connected if and only if for any distinct x, y vertices in the graph, there are k internally disjoint paths from x to y in the graph

This makes me think that a k-connected graph is also a k-1 connected graph, since if it's k-connected there must exist k internally disjoint paths (which implies there must exist k-1 internally disjoint paths which means it must also be k-1 connected). Is this true? Or am I missing something?

  • $\begingroup$ Yes............ $\endgroup$ Nov 26, 2017 at 18:30

1 Answer 1


Yes, this is the typical terminology. If you want to refer to the unique maximal k so that a graph is k-connected, you call it the connectivity. So a k-connected graph is (k-1)-connected, but a graph with connectivity k can't be said to have connectivity k-1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.