$G$ is a graph on $n$ vertices and $2n−2$ edges. The edges of $G$ can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G$?
- For every subset of $k$ vertices, the induced subgraph has at most $2k−2$ edges.
- The minimum cut in $G$ has at least $2$ edges.
- There are at least $2$ edge-disjoint paths between every pair of vertices.
- There are at least $2$ vertex-disjoint paths between every pair of vertices.
My attempt:
Counter for option $(4)$ is as follows: Take two copies of $K_4$(complete graph on $4$ vertices), $G_1$ and $G_2$. Let $V(G_1)=\{1,2,3,4\}$ and $V(G_2)=\{5,6,7,8\}$. Construct a new graph $G_3$ by using these two graphs $G_1$ and $G_2$ by merging at a vertex, say merge $(4,5)$. The resultant graph is two edge connected, and of minimum degree $2$ but there exist a cut vertex, the merged vertex.
Can you explain in formal/alternative way, please?
Is true. Take the subgraphs induced by the two spanning trees, these have $k$ vertices and are cycle-free. Any cycle-free graph with k vertices has at most $k-1$ edges.
Is true. Let $v, w$ be vertices from different sets of the cut. Then by 3. there are two edge-distinct paths between $v$ and $w$. So at least one of the edges of each path needs to be cut.
Is true. The two spanning trees give two distinct paths which are edge-disjoint since the spanning trees are edge-disjoint.
Your counter-example goes through.