0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jan 30, 2016 at 11:21

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .