connectivity and graph construction this might be very stupid question for regular maths students, but I had the following thought after reading about $2$ connected graphs, and thought about asking it. Now $G$ is $2$ connected is equivalent to (for a cycle $C$) $C = G_1\subset G_2\ldots G_n = G$, where $G_{i+1}$ is obtained from $G_i$ by addition of $G_i$ path. Two questions which I had are:


*

*Is it true that any graph $G$ can be obtained in this way, that is $\tilde{C} = G_1\subset G_2\ldots G_n = G$ where $G_{i+1}$ is obtained from $G_i$ by addition of $G_i$ path, and $\tilde{C}$ is not necessarily a cycle but some structure. (assume $n$ can be varied, how $n$ is decided is assume we do not know).

*if the above is true, then is connectivity determined by essentially the underlying structure $\tilde{C}$ ?
 A: This is not true, as will be shown below. However, there is a related theorem due to Tutte, which characterizes $3$-connected graphs.
A graph $G$ is $3$-connected iff there exists a sequence $G_0 \subseteq G_2 \subseteq \dots G_n$ such that:
(1) $G_0 = K^4$ and $G_n = G$.
(2) $G_{i + 1}$ has some edge $e$ such that $G_i = G_{i + 1} \dot - e$, for every $0 \le i < n$.
The graph $G \dot - e$ is defined to be the multigraph formed from $G - e$ by suppressing the endpoints of $e$ which have degree two.
Suppressing a vertex $v$ of degree two is defined by deleting $v$ from the graph, and adding an edge between the two neighbours of $v$.
Clearly, this is not quite the same thing as simply starting with $K^4$ and adding $G_i$-paths, so the answer to your first question is not true in the way that you seem to mean it.
Trivially, of course, any graph $G$ can be defined to be equal to $\overline C$, giving that for $n = 1$, $\overline C = G_1 = G$.
As to your second question, I don't know that anyone really knows. The $2$ and $3$-connected graphs have complete characterizations of this form, and it is easy to construct a similar characterization of $1$-connected graphs, but I am unaware of any such characterization of graphs with higher connectivity.
