Answer to Question #142151 in Discrete Mathematics for Chetan pawar

Question

Q.Which of the following can be a degree sequence of a simple graph?

{4,4,3,2,1}


{4,3,2,1}


{4,4,3,2}


{4,2,2,2,2}

Q.If G is a connected simple graph and e,f and g are edges of G, then which of the following is/are true:

There is always a spanning tree of G that contains e


There is always a spanning tree of G that contains e and f


There is always a spanning tree of G that contains e,f and g


All of the above.
Q.If G is a simple, disconnected graph on n vertices, how many maximum edges can it have?

n−2


(n2)


(n−12)


(n−12)+1
Q.Which of the following statements is NOT true?

The maximum number of cut vertices in any simple, connected graph on n vertices is n−2


If there exist a cut-edge in the graph, then a cut-vertex must also exist.


If there exist a cut-vertex in the graph, then a cut-edge must also exist.


The maximum number of cut-edges in any simple graph on n vertices is n−1.

Answer 1

1) {4,3,2,1}

The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. 

2)There is always a spanning tree of G that contains e,f and g

A tree is said to be a spanning tree of a connected graph G, if T is a subgraph of G and T contains all vertices of G.

3)$\begin{pmatrix} n-1\\ 2 \end{pmatrix}$

Let graph has n vertices from which one node is disconnected, maximum number of edges between the remaining n−1 nodes can be $\begin{pmatrix} n-1\\ 2 \end{pmatrix}$

4)If there exist a cut-vertex in the graph, then a cut-edge must also exist.

 If a cut vertex exists, then the existence of any cut edge is not necessary.