<p>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 <em>connectivity</em>. So a k-connected graph is (k-1)-connected, but a graph with connectivity k can't be said to have connectivity k-1.</p>

CC BY-SA 3.0
2017-11-22T01:54:02.327Z
2017-11-22T01:54:02.327Z
daveagp
<p>So I'm reading about k-connected graphs, and I'm a little confused about them. This is the main definition I've seen:</p>

<p>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</p>

<p>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?</p>

CC BY-SA 3.0
2017-11-26T18:30:33.217Z
Yes............
András Salamon
<graph-theory>
Is a k-connected graph also k-1 connected?
user47595
# Is a k-connected graph also k-1 connected?

(Asked by: username_0 on 2017-11-22)

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?

**Tags:** graph-theory

> **Comments:**
> **username_1**: Yes............  

---

## 1 answers

### Answer by username_2 on 2017-11-22. Score: 2

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.


---

