Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path.

A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, and for every pair of distinct vertices, $u$ and $v$, $d(u)+d(v)+d(u,v)\geq t$, where $d(u)$ is the degree of vertex $u$ and $d(u,v)$ is the distance from $u$ to $v$. Locke et al. [2] show that every $2k$-cohesive graph contains a non-separating path on $k$ vertices.

My question: what is the connection between connectivity and cohesion of a graph? Any existing results about the condition of non-separating path on $k$ vertices (except the above mentioned one)? Especially the condition which combines connectivity and cohesion together. (In the existing literature, there are some results of cohesive structure in social networks, which is different from the definition above.)

[1] Tutte, W. T.: How to draw a graph, Proc. London Math. Soc., 13 (1963), 743–767.

[2] Locke, Stephen C., Phil Tracy, and H-J. Voss. "Highly Cohesive Graphs Have Long Nonseparating Paths: 10647." American Mathematical Monthly (2001): 470-472.


A k-connected graph G, k>0, will be (2k+1)-cohesive. However, one can easily construct a (2k+1)-cohesive graph which is only 1-connected: take two disjoint copies of complete graphs and add one edge between them.

Other references on cohesion (a name I believe Doug West coined as an editor of the problems column):

M. Abreu and S.C. Locke. Non-separating n-vertex trees in (2n+2)-cohesive graphs of diameter at most 4. Congressus Numerantium 154(2002), 21-30. [MR#2004e:05102]

C. Gottipati and S.C. Locke. Cohesion and non-separating trees in connected graphs, submitted to the Journal of Combinatorial Mathematics and Combinatorial Computing. Accepted in 2015.

Ajit A. Diwan and Namrata P. Tholiya, Non-separating Trees in Connected Graphs, Discrete Mathematics 309 (2009) 5235-5237.

  • $\begingroup$ Thank you very much! It is a big surprise to get the answer from the original author! $\endgroup$
    – user39815
    Sep 27 '16 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy