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

812 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

Your construction is indeed a counter-example.
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.