I need help proving that every minimally 2-connected graph has a vertex of order 2 (the order of a vertex being equal to the number of edges that "enters" it).
By definition, a graph is 2-connected, if for every vertex $x, x
\in V(G), G- x$ is connected.
Minimally 2-connected graphs have the property that they are 2-connected graphs but when an edge is removed from them, they become 1-connected graphs.
I've seen from other posts that if I can show that all minimally 2-connected graphs can be formed by adding paths between vertices of a cycle graph, then I should have my answer.
However, I am not sure how to show this. Is this also even the right approach?
Many thanks
Best Answer
What you mention is close to the ear-decomposition of 2-connected graphs: the edge set of any 2-connected graph can be partitioned into $C_0, P_1, \ldots, P_k$ where $C_0$ is a cycle, $P_1$ is a path between distinct nodes of $C_0$, $P_i$ is a path between distinct nodes of $C_0 \cup P_1 \cup \ldots \cup P_{i-1}$. However notice that the paths (except $P_1$) are not forced to have their endpoints in $C_0$. Also, one can easily show that if a graph has an ear decomposition, it is 2-connected.
Given $G$ a minimally 2-connected graph, we want to prove that there is an ear decomposition of $G$ where the last path $P_k$ has length at least $2$. Indeed any inner vertex of $P_k$ has degree 2 in $G$, so it is sufficient to prove that there is at least one inner vertex. Take any ear decomposition $C_0 \cup \ldots \cup P_k$ of $G$. If $P_k$ is a single edge $e$, then $G \setminus \{e\} = C_0 \cup P_1 \cup \ldots \cup P_{k-1}$ has an ear-decomposition, hence it is 2-connected. This contradicts the fact $G$ is minimally 2-connected. Hence $P_k$ has at least one inner node.
Here is another proof that does not use ear-decomposition:
Take a cut $\delta(S)$ with a shore $S \subseteq V$ such that $d(S) = 2$ and $|S|$ is minimum, and show that $|S| = 1$.
Suppose that there is an edge $uv \in E[S]$. By minimality of $G$, there is a cut $S'$ with $uv \in \delta(S')$ and $d(S') = 2$. By minimality of $|S|$, $S' \nsubseteq S$. By submodularity of the cut function, $$ 4 = d(S) + d(S') \geq d(S \cup S') + d(S \cap S') \geq 4$$ where the last inequality comes from the fact that each cut has cardinal at least 2. We deduce that all the inequalities must be tight, hence $d(S \cup S') = d(S \cap S') = 2$. But $|S \cap S'| < |S|$ (as either $u$ or $v$ is not in $S'$), contradicting the minimality of $|S|$.