Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

  1. 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).

  2. if the above is true, then is connectivity determined by essentially the underlying structure $\tilde{C}$ ?

share|cite|improve this question

migrated from Nov 8 '13 at 3:49

This question came from our site for professional mathematicians.

up vote 2 down vote accepted

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.

share|cite|improve this answer
i agree that the operation which you described in Tutte's theorem is not the same as starting with $K_4$ and building paths….but there might be some other graph with which you can start..I mean if you draw any graph you obviously start with some base graph and then keep adding $G_i$ paths……?….somehow Menger's theorem suggested to me that start with $k$ disjoint paths, and then keep adding $G_i$ paths…. – user24367 Nov 8 '13 at 5:07
As I said in the second-to-last paragraph, it's always possible to make a construction like this, or, alternately, starting with no edges, and simply adding '$G_i$-paths' consisting of single edges. However, the base graph cannot characterize the connectivity of the graph in the general case, as the addition of a $G_i$ path that is longer than a single edge will necessarily cause the resulting $G_{i + 1}$ to be at most $2$-connected, and given some base graph $G$, it is possible to construct graphs of any connectivity at least the connectivity of $G$ by adding edges. – qaphla Nov 8 '13 at 5:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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