edited by
698 views
5 votes
5 votes

Which of the following statements is FALSE?

  1. If G(e,v) is a connected bipartite planar graph and $v \geq 3$ , then $e \leq 2v - 4$.
  2. $3,3,2,2,2,2$ is a graphic sequence.
  3. In a simple graph with at least two vertices, there must be two vertices that have the same degree.
  4. An edge set S is called ‘cut set’ if removal of edges from S disconnects the graph.
edited by

3 Answers

1 votes
1 votes

A cut set is a set of edges whose removal disconnects the graph. All the edges together form the cut set — any proper subset of edges from the cut-set won't disconnect the graph.

So, Option D


More:-

  • A cut vertex is a single vertex whose removal disconnects the graph.
    A cut vertex is also called an articulation point.
     
  • A cut edge is a single edge whose removal disconnects the graph.
    A cut edge is also called a bridge.
0 votes
0 votes

The statement "An edge set S is called 'cut set' if removal of edges from S disconnects the graph" is wrong because it is not necessary for a cut set to contain all of the edges that disconnect the graph. A cut set can contain only a subset of the edges that disconnect the graph, as long as removing that subset of edges disconnects the graph.

For example, consider the following graph:

A -- B
|   |
C -- D

This graph is connected, and the edge set {AB, CD} is a cut set. However, removing only one of these edges, say AB, does not disconnect the graph. The graph is still connected, with vertices A and C connected through vertex B. It is only when both AB and CD are removed that the graph is disconnected.

Therefore, a more accurate definition of a cut set is:

A cut set of a connected graph G is a subset of the edges of G such that removing all of the edges in the subset disconnects G.

Answer:

Related questions

5 votes
5 votes
2 answers
1
Bikram asked May 24, 2017
567 views
Let $S$ be the set $\{1,2,3, \dots ,8\}$. Let $n$ be the number of sets of two non-empty disjoint subsets of $S$. The value of $n$ is _______.
5 votes
5 votes
1 answer
2
Bikram asked May 24, 2017
477 views
Total number of ways we can fill a $4 \times 4$ matrix by $0$ and $1$’s such that every row and column contains odd no of $0$'s and $1$'s is ________.
2 votes
2 votes
1 answer
3
Bikram asked May 24, 2017
218 views
What is the solution of the following recurrence relation? $a_n = 6.a_{n-1} - 9.a_{n-2}$ Base cases : $a_0 = 1$ and $a_1 = 6$.$3n$$2.3n$$3n + n.3n$$3n - n.3n$
2 votes
2 votes
2 answers
4
Bikram asked May 24, 2017
387 views
Which of the above is a lattice :b and ca and db and da only