Here arer some true and false question. please help me 1. Let G be an undirected

Question

Here arer some true and false question. please help me

1. Let G be an undirected graph. We use m and n to denote the number of edges and vertices, respectively.

(1) For G, the maximum possible value of m is n(n + 1).
(2) If G is connected and has exact n 1 edges, then Q has no cycle.

2. Let G be a directed graph and Q a undirected graph. We use m and n to denote the number of edges and vertices, respectively.

(1) If G is strongly connected, then m 2(n 1).
(2) For Q, the maximum possible value of m is n(n + 1).
(3) If Q is connected and m = n 1 edges, then Q has no cycle.

you could answer within or without explaination, thanks

Explanation / Answer

1.

1) For G, the maximum possible value of m is n(n + 1) is False statement.....

consider A B C vertices..Three vertices connected in 3 ways..ie (A,B),(A,C),(B,C)

but you given formula 3(3+1)==12 edges which is false..

Correct formula is n(n-1)/2 ==>3(3-1)/2==>6/2==3

2) If G is connected and has exact n - 1 edges, then Q has no cycle. Yes it is true.

Let us prove by contraverse...i mean reverse..Assume condition if false..so if we remove edge then it will be connected. so keep on doing on this..we will have edges such that v-1>v-1 which is not possible. so it is false...therfore the required statement is true.

2

1) & 2) are false statements..

the..for n vertices..there wil be n-1 edges...so maximum possible edges are n(n-1)

3)false statement...this statement is valid for undirected graph..which was already proved in above question.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.