in Graph Theory edited by
23,234 views
76 votes
76 votes

$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.
in Graph Theory edited by
23.2k views

4 Comments

Any cyclic graph makes d false
0
0
I am not able to visualize this question.
0
0

Edge disjoint spanning trees are spanning trees that do not have any edges in common. 

3
3

6 Answers

63 votes
63 votes
Best answer

There are $2$ spanning trees (a spanning tree connects all $n$ vertices) for $G$ which are edge disjoint. A spanning tree for $n$ nodes require $n-1$ edges and so 2 edge-disjoint spanning trees requires $2n-2$ edges. As $G$ has only $2n-2$ edges, it is clear that it doesn't have any edge outside that of the two spanning trees. Now lets see the cases:

Lets take any subgraph of $G$ with $k$ vertices. The remaining subgraph will have $n-k$ vertices. Between these two subgraphs (provided both has at least one vertex) there should be at least $2$ edges, as we have $2$ spanning trees in $G$. So, (B) is TRUE. Also, in the subgraph with $k$ vertices, we cannot have more than $2k-2$ edges as this would mean that in the other subgraph with $n-k$ vertices, we would have less than $2n-2k$ edges, making $2$ spanning trees impossible in it. So, (A) is also TRUE.

A spanning tree covers all the vertices. So, $2$ edge-disjoint spanning trees in $G$ means, between every pair of vertices in $G$ we have two edge-disjoint paths (length of paths may vary).  So, (C) is also TRUE.

So, that leaves option (D) as answer. It is not quite hard to give a counter example for (D).

edited by
by

4 Comments

edited by
If n = 1, you have only one spanning tree (the root). This violates the condition of having two spanning trees given in question. The smallest graph which satisfies this question is the complete graph on 4 vertices
0
0
How to come up with counter examples in the exam?
0
0
U can't, u have to leave it and go 🫠
1
1
26 votes
26 votes

Plz see below graph

Here it satisfies all constraints 2n-2 edges. 2 edge-disjoint spanning trees.

Imp:->> (in addition to some graphs shown like above )All wheel graphs with odd no. of nodes satisfy above 2  given constraint of question.

And now elimnate options.

(I think for option B if they will tell minimum cut edge is atleast 3 then also it is true..plz verify But atleast 2 includes atleast 3)

All options are true except D due to presence of cut vertex.

Note:- Edge-disjoint path :- pair of nodes can be connected by 2 diffrent paths which dont have any shared edges.

Vertex-disjoint path;--pair of nodes can be connected by 2 diffrent paths which dont have any shared vertices(nodes).

edited by

3 Comments

@rajesh pradan your 2nd graph is not spanning tree...u cant traverse all vertices in one go..
–1
–1

spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G.

I think the definition  of spanning tree satisfy G2.

n=8V  (n-1 =7 edges  and no cycles which denotes a tree) and cover all Vertices. As well subgraph of G.

0
0

For option b if it says atleast three edges then it will be wrong as shown in picture if cut is taken as only vertex 10 and other contains remaning vertices then minimum cut has only 2 edges..

And this option says that every vertex has degree of atleast 2 and it is indeed true becaus There is two Spanning trees possible with disjoint edge set.  

2
2
18 votes
18 votes

(A) satisfies here. Induced subgraph is a connected graph which is subgraph of main graph

(B) This is possible. It is a complete graph,So, if we remove only 1 edge the graph is not disconnected.Min cut must be atleast 2 edges.

(C) yes for every vertices there are two edge disjoint path

So, (D) is the ans. If u eliminate any two vertex , no edge will be disconnected.(conter example given by @Akash)

edited by

4 Comments

@srestha

I think example given by you is wrong for n vertices there should be 2n-2 edges

In your example n=8 so there should be 14 edges , but in your example there are 12 edges

0
0
Your Graph is not as per the question.

No of edges are less.
0
0

@ the two graphs need to merged at a vertex, then only it will satisfy the condition given in the question, which is : n vertices and 2*n-2 edges

0
0
15 votes
15 votes

(A)For the case k=n, the induced sub-graph is the graph itself and it has $2n-2$ edges.

(B)Given from the description of the graph,G it has two edge-disjoint spanning trees.

Now there is a theorem which says, The cut-set of a connected graph G must contain at least one edge from every spanning tree of Graph G.

This graph has two edge-disjoint spanning trees and hence, this graph's cut-set would have minimum size of 2.(one-edge from each of the spanning tree). Note that, here we don't mean that the cut-set size is 2, but it means atleast 2.

So, this is true.

(C)Since there are two edge-disjoint spanning trees of G, there are indeed 2 edge-disjoint paths between every pair of vertices.

This is true.

Answer-(D)

4 Comments

Yeah, for that you should have some spare vertices and edges.
0
0
yes
0
0
i dont think we will ever have some spare vertices bcoz  every vertex will be included in the first spanning tree only.
1
1
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true