Nice result; see here.

We present a solution different from those in the thread linked above. Let $G$ be our graph. Call a pair $(X,Y)$ of connected subgraphs of $G$ to be separating iff $X\sqcup Y=G.$ We induct on $n.$ For $n\le 4$ the statement can be checked by hand. Suppose now that $n\ge 5$ and that we have already proved the problem for any smaller number of vertices. Case 1. For any $\overline{ab}\in E(G)$, $G-\{a,b\}$ is connected. In this case, any $\overline{ab}\in E(G)$ yields a separating pair $(\{a,b\}, G-\{a,b\})$. Since $n\neq 4$, no such pair is of the form $(\{a,b\},\{c,d\})$, implying that each edge gives a different separating pair. Overall, we have at least $E(G)$ separating pairs. Case 2. There is some $\{a,b\}\in E(G)$ such that $G-\{a,b\}$ is not connected. Suppose that $G-\{a,b\}$ is partitioned into connected components $G_1,G_2,...,G_t$, $t\ge 2$. Each such component must be connected to at least one of $a$ and $b.$ Say, without loss of generality, that $G_1$ is connected only to $a.$ $G_1\cup \{a\}$ is connected, so by the induction hypothesis, there are at least $E(G_1\cup\{a\})$ separating pairs $(X,Y)$ of $G_1\cup\{a\}$, with $a\in V(X).$ For each such pair, $(\{b\}\cup G_2\cup...\cup G_t\cup X, Y)$ is a separating pair of $G.$ Similarly, $G-G_1$ is connected, so by the induction hypothesis there are at least $E(G-G_1)$ separating pairs $(X, Y)$ of $G-G_1$, with $a\in V(X).$ For each such pair, $(G_1\cup X, Y)$ is a separating pair of $G.$ We now check that all obtained pairs are different. a) $(\{b\}\cup G_2\cup...\cup G_t\cup X_1, Y_1)= (\{b\}\cup G_2\cup...\cup G_t\cup X_2, Y_2)$, where $(X_1,Y_1)$ and $(X_2,Y_2)$ are separating pairs of $\{a\}\cup G_1.$ Clearly $X_1=X_2$ and $Y_1=Y_2$ in this case. b) $(G_1\cup X_1, Y_1)=(G_1\cup X_2, Y_2)$, where $(X_1,Y_1)$ and $(X_2,Y_2)$ are separating pairs of $G-G_1.$ Clearly $X_1=X_2$ and $Y_1=Y_2$ in this case. c) $(\{b\}\cup G_2\cup...\cup G_t\cup X_1, Y_1)=(G_1\cup X_2, Y_2)$, where $(X_1,Y_1)$ and $(X_2,Y_2)$ are separating pairs of $\{a\}\cup G_1$ and $G-G_1$, respectively. Then $X_1-\{a\}=G_1\cap (\{b\}\cup G_2\cup...\cup G_t\cup X_1)=G_1\cap (G_1\cup X_2)=G_1$, so $X_1=\{a\}\cup G_1$, i.e. $Y_2=\emptyset$, contradiction! Also note that the first component always contains $a$ as a vertex, so we don't have to worry about equalities of the type $(X_1,Y_1)=(Y_2,X_2)$. Therefore, overall we have at least $E(\{a\}\cup G_1)+E(G-G_1)=E(G)$ distinct separating pairs of $G.$ Suppose now that each of $G_1,G_2,...,G_t$ is connected to both $a$ and $b$. $G_1\cup\{a,b\}$ is connected, and by the induction hypothesis this subgraph has at least $E(G_1\cup\{a,b\})$ separating pairs $(X,Y)$ with $a\in V(X).$ For each such pair, $(G_2\cup...\cup G_t\cup X, Y)$ is a separating pair of $G.$ Similarly, $G-G_1$ is connected, and by the induction hypothesis this subgraph has at least $E(G-G_1)$ separating pairs $(X,Y)$, with $a\in V(X).$ For each such pair, $(G_1\cup X, Y)$ is a separating pair of $G.$ We now check whether we have any repetitions in the obtained pairs. a) $(G_2\cup...\cup G_t\cup X_1, Y_1)=(G_2\cup...\cup G_t\cup X_2, Y_2)$, where $(X_1,Y_1)$ and $(X_2,Y_2)$ are separating pairs of $G_1\cup\{a,b\}$. Clearly $X_1=X_2$ and $Y_1=Y_2$ in this case. b) $(G_1\cup X_1,Y_1)=(G_1\cup X_2,Y_2)$, where $(X_1,Y_1)$ and $(X_2,Y_2)$ are separating pairs of $G-G_1$. Then $X_1=X_2$ and $Y_1=Y_2$ in this case. c) $(G_1\cup X_1, Y_1)=(G_2\cup...\cup G_t\cup X_2, Y_2)$, where $(X_1,Y_1)$ and $(X_2,Y_2)$ are separating pairs of $G-G_1$ and $G_1\cup\{a,b\}$, respectively. Then, $\{a\}\cup G_1=(\{a\}\cup G_1)\cap (G_1\cup X_1)=(\{a\}\cup G_1)\cap (G_2\cup...\cup G_t\cup X_2)=(\{a\}\cup G_1)\cap X_2$, so $\{a\}\cup G_1\subseteq X_2.$ As $Y_2\neq\emptyset$, we must have $X_2=\{a\}\cup G_1$ and $Y_2=\{b\}$, and so $Y_1=\{b\}$, $X_1=G-(G_1\cup\{b\})$. Thus, we have at most one equality occurring in this case. Also note that the first component always contains $a$ as a vertex, so we don't have to worry about equalities of the type $(X_1,Y_1)=(Y_2,X_2)$. Therefore, we have at least $E(G_1\cup\{a,b\})+ E(G-G_1)-1=E(G)$ distinct separating pairs of $G$. This ends our proof.

Given a simple$,$ connected graph with $n$ vertices and $m$ edges$.$ Prove that one can find at least $m$ ways separating the set of vertices into two parts$,$ such that the induced subgraphs on both parts are connected$.$

Let $G=(V,E)$ be the graph. We will show that for each edge $e\in E$ there is a different partition $V=V_{1}\cup V_{2}$ such that the induced subgraphs of $V_{1}$ and $V_{2}$ are connected. Consider a BFS spanning tree $T$. For the edge $e=uv$ we have two cases: $e\in T$ - if $v$ is the deeper vertex, let $V_{1}$ be the subtree of $v$ and $V_{2}=V\backslash V_{1};$ $e\notin T$ - the subtrees $T_{1}$ and $T_{2}$ of $u$ and $v$ are disjoint. Let $V_{1}=T_{1}\cup T_{2}$ and $V_{2}=V\backslash V_{1}$. It is obvious that all the partitions are different and split $G$ in two connected subgraphs.

@above: BFS (Breadth First Search) spanning tree is taken only to ensure all the edges of $G$ that are not edges in $T$ are cross edges in $T$. But, this is not so essential. You can take any spanning tree $T.$ For edges $e\in T$ the partition is the same. Suppose $e\notin T$ and $e=uv.$ If $u$ and $v$ are not comparable (i.e. $uv$ is a cross edge) then the partition is the same as above. If $u,v$ are comparable and $u=v_0,v_1,v_2,\dots,v_n, v_{n+1}=v$ is the path along $T$ from $u$ to $v$ then we take $V_1:=\{v_1,v_2,\dots,v_n\}, V_2:=V\setminus V_1.$ EDIT: It's not properly written, see #8 for the right construction.

Wrong - consider a graph on four vertices with edges $v_{1}v_{2}$, $v_{2}v_{3}$, $v_{3}v_{1}$, $v_{2}v_{4}$ and spanning tree rooted at $v_{1}$ with edges $v_{1}v_{2}$, $v_{2}v_{3}$, $v_{2}v_{4}$ - then in your construction for the edge $v_{1}v_{3}$ we have $V_{2}=\{v_{1},v_{3},v_{4}\}$ which is not connected.

Ok, my bad, it's wrong the way I wrote it, but the idea is still there and you do not need BFS, you just need a spanning tree. Let me rewrite it again, the difference is at the end. @above: BFS (Breadth First Search) spanning tree is taken only to ensure all the edges of $G$ that are not edges in $T$ are cross edges in $T$. But, this is not so essential. You can take any spanning tree $T.$ For edges $e\in T$ the partition is the same. Suppose $e\notin T$ and $e=uv.$ If $u$ and $v$ are not comparable (i.e. $uv$ is a cross edge) then the partition is the same as above. If $u,v$ are comparable and $u=v_0,v_1,v_2,\dots,v_n, v_{n+1}=v$ is the path along $T$ from $u$ to $v$ then we delete the edges $v_0 v_1$ and $v_nv_{n+1}.$ Thus, we partition the vertices into two connected graphs. On the other hand, given this partition, we can recover the edge that generated it. So, it's an injection between the edges and the partitions.

Again wrong - if we consider $K_{4}$ and the spanning tree $v_{1}v_{2}$, $v_{2}v_{3}$, $v_{3}v_{4}$ with root $v_{1}$ for the edge $v_{1}v_{3}$ after deleting the two edges the graph remains connected.

It doesn't matter the graph is still connected. Consider the graph $G_1$ that consists of the tree $T$ plus the edge $uv$. Delete the edges $v_0v_1$ and $v_nv_{n+1}$. After this operation, $G_1$ falls apart into two connected graphs with vertices $V_1$ and $V_2$. This is the wanted partition. Btw, you did exactly the same trick in your post #5 when $uv$ is a cross edge. Actually, we do not need to separate these two cases. Just take the (unique) path along the tree $T$ that connects $u$ and $v$ and do what I described. Did you finally get it?

We proceed by strong induction. Case 1: The graph contains a bridge. Suppose $ab$ is a bridge, then let $G_1$ be the set of vertices that need to use $a$ to go to $b$, and let $G_2$ be the rest of the vertices. For each way to split $G_1$, we add $G_2$ to the part containing $a$. For each way to split $G_2$, we add $G_1$ to the part containing $b$. Finally, $G_1, G_2$ is another way. Case 2: The graph doesn't contain a bridge. This implies every edge is in a cycle. It suffices to show that we can delete two vertices $xy$ sharing an edge such that the graph is still connected because this invalidates having $xy$ as a part. We first make the circular optimization: if removing an edge doesn't create a bridge, we remove the edge. If after that, the statement is still true, the statement must be true here, as adding edges don't disconnect the graph. Therefore, each edge is part of exactly one cycle. Two cycles can obviously share at most one vertex, since if two cycles share an edge, removing this edge won't create a bridge. Let's think about how this graph is "built". Initially, there is a cycle. For an edge to fail, there must exist another cycle using that vertex. However, that cycle also has an edge that works. If at any time it fails, note that at least two vertices are already used, but we are using completely new vertices, or we get an edge in two cycles.

Let $G=(V,E)$ be a connected graph. A set $S \subseteq E$ of edges is an \textbf{edge-cut} of $G$ if $G-S$ is disconnected. Note that each edge-cut yields a partition of $V$, with the connected components of the edge-cut being the parts of the partition. A \textbf{bond} is a minimal edge-cut, and the partition associated to a bond always has exactly two parts. Further, two bonds never induce the same partition (we note that every cut-edge is itself a bond). If $H$ is a subgraph of $G$, then a \textbf{bridge} of $H$ in $G$ is a subgraph of $G$ formed by taking both a connected component $C$ of $G-H$, and all the edges and vertices of $H$ to which that component is incident / adjacent. Note that every edge of $E(G)-E(H)$ lies in exactly one bridge of $H$. Further, every bridge is itself a connected graph. \begin{figure}[h] \centering \includegraphics[width=\textwidth]{Bridges} \caption{A graph $G$ with a subgraph $H$, and the three bridges of $H$ in $G$.} \end{figure} \section{The main act} \begin{thm} If a connected graph has $m$ edges, then it has at least $m$ bonds (and thus has at least $m$ partitions into two connected subgraphs). \end{thm} \begin{proof} By inspection, the theorem is true for all connected graphs with $n\leq 4$ vertices (there are very few graphs to check here). We prove the theorem by non-existence of a minimal counter-example. Assume to the contrary there is a counter-example. Let $n$ be the smallest number of vertices that any counter-example has, and note $n> 4$. Among all counter-example graphs on $n$ vertices, let $G=(V,E)$ be a counter-example with the minimum number $m$ of edges. Specifically, all connected graphs with fewer vertices than $G$, or as many vertices and fewer edges than $G$, have at least as many bonds as edges. Note that the minimum number of edges of a connected graph of order $n$ is $n-1$. Any graph with this number of edges is a tree, and every edge of a tree is its own bond, so we know $m\geq n$. \textbf{Claim 1:} The graph $G$ has no cut-vertex. Assume to the contrary $v$ is a cut vertex of $G$, and let $B_1, \dots, B_k$ be the bridges of $\{v\}$ in $G$. Note that every edge of $G$ lies in exactly one of these, so $|E(B_1)| + \dots + |E(B_k)| = m$. Any bond of one of these bridges is a bond of the whole graph, so by minimality of $G$, the bridge $B_i$ has at least $|E(B_i)|$ bonds, each of which is a bond of the whole graph. The bonds in two different bridges share no edges in common, so no bonds from two different bridges overlap. Thus the graph $G$ has at least $|E(B_1)| + \dots + |E(B_k)| = m$ bonds. This contradiction proves the claim. We note as a result of Claim 1 that $G$ also does not contain any cut-edge, since every cut-edge in a graph of order $3$ or more is incident with at least one cut-vertex. \textbf{Claim 2:} There exists an edge $uv$ of $G$ such that $G-\{u,v\}$ is not connected. Assume to the contrary that for every edge $uv$, $G-\{u,v\}$ is connected. Consider the partition of $V$ given by $\{u,v\} \sqcup (V-\{u,v\})$, and note that there is a bond $S_{uv}$ that induces this partition (this bond just contains all the edges that have one end in $\{u,v\}$ and the other end not in $\{u,v\}$). The set $\{S_{uv} : uv\in E\}$ contains a distinct bond for every edge of $G$, so $G$ has at least $m$ bonds. This contradiction proves Claim 2. Now we let $uv$ be an edge of $G$ such that $G-\{u,v\}$ is not connected (which exists by Claim 2). We call $H$ the subgraph of $G$ consisting of just the vertices $u$ and $v$ and the edge $uv$, and note that since $G-H$ is disconnected, $H$ has at least two bridges. Since $G$ has no cut-vertex by Claim 1, all the bridges of $H$ contain both $u$ and $v$, so each bridge contains $H$. Let $B_1$ be one of the bridges of $H$, and let $B_2$ be the subgraph of $G$ formed by taking the union of every bridge of $H$ except for $B_1$. Note that $G\subseteq B_1\cup B_2$, and $B_1\cap B_2 = H$. \begin{figure}[h] \centering \includegraphics[width=200pt]{fig1} \caption{The graph $G$ can be divided up into a bridge $B_1$, and a collection of bridges $B_2$, where $B_1 \cap B_2 = H$.} \end{figure} Let $m_1 = |E(B_1)|$ be the number of edges in $B_1$, and $m_2 = |E(B_2)|$ be the number of edges in $B_2$. Every edge of $G-uv$ lies in either $B_1$ or $B_2$, and these two subgraphs share exactly the edge $uv$, so $m_1 + m_2 = m + 1$. \textbf{NB:} Note that any bond of $B_1$ (or $B_2$) that does not contain the edge $uv$ must be a bond of the whole graph $G$ By the minimality of $G$, the connected subgraph $B_1$ has a set $X_1$ of least $m_1$ bonds, and $B_2$ has a set $X_2$ of at least $m_2$ bonds. Let $Y_u$ be the set of edges of $B_1$ incident with $u$, and $Z_u$ the set of edges of $B_2$ incident with $u$. If it is possible to choose either the set $X_1$ (or $X_2$) such that no bond in $X_1$ (or $X_2$) contains the edge $uv$, then by just taking all the bonds of $X_1$ ($X_2$) as they are, all the bonds of $X_2$ ($X_1$) not containing $uv$ as they are, and adding to all the bonds of $X_2$ ($X_1$) that do contain $uv$ the set $Z_u$ ($Y_u$), we get a collection of $m+1$ distinct bonds of the whole graph $G$, which is a contradiction. Thus both $X_1$ and $X_2$ both have at least one bond containing the edge $uv$. Let $j_1$ and $j_2$ be the number of bonds not containing $uv$ in $X_1$ and $X_2$ respectively, and note that every one of these bonds not containing $uv$ is itself a bond of the whole graph $G$. Let $k_1$ and $k_2$ be the number of bonds that do contain $uv$ in $X_1$ and $X_2$ respectively. Collecting facts from the previous two paragraphs: \begin{itemize} \item $|X_1| = j_1 + k_1$, \item $|X_2| = j_2 + k_2$, \item $|X_1| \geq m_1$, \item $|X_2| \geq m_2$, \item $m_1 + m_2 = m+1$, \item $k_1, k_2 \geq 1$. \end{itemize} Any bond $S$ of the $k_1$ bonds of $X_1$ containing the edge $uv$ is just a bond that has $u$ and $v$ in different components (and same for the $k_2$ bonds in $X_2$). These two components are joined together by some path in $B_2$, so $S$ is not a bond of $G$. However, if we take any bond $T$ of $B_2$ that also contains $uv$, then the edge-cut $S\cup T$ is a bond of $G$. \begin{figure}[h] \centering \includegraphics[width=200pt]{fig2} \caption{If $S$ is a bond of $B_1$ containing $uv$, and $T$ is a bond of $B_2$ containing $uv$, then $S\cup T$ is a bond of $G$.} \end{figure} Any of the $k_1$ bonds of $B_1$ with $uv$ can be unioned with one of the $k_2$ bonds of $B_2$ with $uv$ in this way, and all these possible unions of pairs are distinct. So by taking these unions, we get $k_1\times k_2$ bonds of $G$ containing the edge $uv$. Since $k_1, k_2 \geq 1$, we have $k_1\times k_2 \geq k_1 + k_2 - 1$ (note that if $x,y \geq 1$, then $(x-1)(y-1) \geq 0$ so $xy \geq x+y-1$). We also know all the $j_1$ and $j_2$ bonds are distinct bonds of $G$, and since these do not contain $uv$, they are distinct from our $k_1\times k_2$ `combined' bonds. So adding this all up, we have at least $k_1\times k_2 + j_1 + j_2$ bonds in $G$. Further: \begin{align*} k_1\times k_2 + j_1 + j_2 &\geq k_1 + k_2 - 1 + j_1 + j_2\\ &= (k_1 + j_1) + (k_2 + j_2) - 1\\ &= m_1 + m_2 - 1\\ &= (m+1) - 1\\ &= m \end{align*} So $G$ has at least $m$ bonds, contradicting the assumption that it is a counter-example, and thus completing the proof.

Much easier than I thought, or I was just misunderstanding the problem. Let $G$ be a simple graph. Call a partition $(V_1, V_2)$ of $V(G)$ good if both of the induced subgraph $G[V_1], G[V_2]$ are connected. We prove the results by induction on $|E(G)|$. For the base case $E(G) = |V(G)| - 1$ (since $G$ is connected), deleting any edge $e$ from $G$ divided $G$ into two component, and both of the component are connected. So there are at least $m$ good partition. Now assume that the statement holds for $|E(G)| \le m-1$ ($m \ge n$). We prove that the statement holds for $|E(G)| = m$.

Motivation

If there is a vertex $v$ with $d(v) = 1$. Let $G'$ be the induced subgraph by deleting $v$. By inductive hypothesis, there are at least $|E(G')| = m-1$ good ways to divide $V(G')$ into two set. For each one, add $v$ into one of the set which containing the only neighbor of $v$, then it is correspond to a good partition of $V(G)$. And note that $(\{v\}, V(G)-v)$ is also a good partition. Hence there are at least $m$ partition. Now we assume that $\delta(G) \ge 2$. By inductive hypothesis, there exist at least one partition $(V_1, V_2)$ of $V(G)$ such that both of the induced subgraph $G[V_1], G[V_2]$ are connected. WLOG, $|V_1| \ge 2$ (else $|V(G)| = 2$ and it is trivial). Start with $V_1, V_2$, we perform the algorithm below until there are exactly $2$ vertices in $V_1$. ALGORITHM: (i) If $G[V_1]$ has at least $|V_1|+1$ edge. By inductive hypothesis, there are ar least $|V_1|+1$ good partition. And at least one of the partition $(S, T)$ satisfies $|S|, |T| \ge 2$. Since $G$ is connected. There must be some edges between $S, V_2$ or $T, V_2$. WLOG, say $S, V_2$, then $G[S \cup V_2]$ are connected. Replace $V_1$ by $T$. (ii) If $G[V_1]$ has at most $|V_1|$ edge. If there is a vertex $v$ with degree $1$ (in $G[V_1]$) Then removed $v$ from $G[v_1]$ does not destroy the connectivity. And since $\delta(G) \ge 2$, $v$ has a neighbor in $V_2$, that means $G[V_2 \cup \{v\}]$ is connected. Replace $V_1$ by $V_1-v$. Else $d_{G[v_1]}(v) \ge 2 \ \forall v\in V_1$, then there are at least $1/2(\sum d_{G[V_1]}(v) \ge |V_1|)$. Hence the equality holds. $G[V_1]$ is a cycle. Select an vertex $v$ such that $v$ has a neighbor in $V_2$, remove $v$ from $V_1$. After such an algorithm, let $V_1 = \{u, v\}$. Since $G[V_1], G[V_2]$ is connected, $uv \in E(G)$ and removing $uv$ from $E(G)$ does not destroy the connectivity, say $G'$. By inductive hypothesis, there are at least $|E(G')| = m-1$ good partition, and they are also a good partition in $G$. However, $(\{u, v\}, G(V)-\{u, v\})$ is not a good partition in $G'$. So there are at least $m$ good partition of $G$. Hence the statement holds for $|E(G)| = m$. As desired.