# There are at least 2 vertex-disjoint paths between every pair of vertices?

$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?$

1. For every subset of $k$ vertices, the induced subgraph has at most $2k−2$ edges.
2. The minimum cut in $G$ has at least $2$ edges.
3. There are at least $2$ edge-disjoint paths between every pair of vertices.
4. There are at least $2$ vertex-disjoint paths between every pair of vertices.

My explained as $:$

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 $2$ edge connected, and of minimum degree $2$ but there exist a cut vertex, the merged vertex.

• Please be careful with the tags on questions. This question should not be tagged as computer science. Perhaps you saw it in a CS class? That is not the meaning of the tag - only questions that are directly about computer science should have that tag. This question is purely about mathematics. Jan 30, 2016 at 11:21

Though I don't see why you argue that by talking about edge-connectivity and minimum degree 2 (which is not the case). What you need to do is show that $G_3$ has $2n - 2$ edges, has $2$ edge disjoint spanning trees, but has a cut vertex.