edited by
3,704 views

6 Answers

Best answer
21 votes
21 votes

Statement:

No. of diagonals : $D(n) = \frac{n*(n-3)}{2}$

Step 1:  Basis : for $n=4,$ $\frac{4*(4-3)}{2} = 2$ is true.

Step 2: Inductive Step :

If  $D(k)$ is true. we need to prove $D(k+1)$ is also true.

We add one more vertex to the set of $k$ vertices. Assume added vertex is $C$.

Further assume $C$ will connects vertex $A$ and $B$ to close the polygon. ($A$ and $B$ already exists in k sided polygon)

From $C$, no of pairs to each $k$ vertices = $k$, out of these two will be used to close the polygon, i.e. used as sides of new $(k+1)$ sided polygon. Further more, initial connection (edge or side) between $A$ and $B$ is now becomes a diagonal.

No. of Diagonals in for $(k+1)$ sided polygon = diagonal from $k$ sided polygon + $k - 2 + 1$

$\frac{k*(k-3)}{3} + k-1 \\= \frac{k^{2} - k - 2}{2} \\= \frac{(k+1)(k-2)}{2} \\ \frac{(k+1)((k+1)-3)}{2}$

$\implies  D(k+1)$ holds.

Since, both the basis and the inductive step have been performed, by mathematical induction, the statement $D(n)$ holds for all natural numbers $n>3.$

edited by
10 votes
10 votes
Without induction---

We know that for a simple graph having n vertices, maximum number of edges $=^nC_2=\frac{n(n-1)}{2}$

So for diagonals of a polygon $(n \ge 3)$  we remove the boundary edges..

So $\frac{n(n-1)}{2} -n=\frac{n(n-3)}{2}$
6 votes
6 votes
The correct answer for part (B) is m = 0 and n = 15.

NOTE: For clear understanding just watch Kamala krithivasan mam video lectures on Relations.

3 votes
3 votes

part B M = 1 & N = 15 

for first digraph

R1 = { (a,b),(b,c),(c,a)}

R= {(a,c),(b,a),(c,b)}

R3 =  { (a,b),(b,c),(c,a)}

so for first digraph m=1 and n = 3

similarly for second digraph  we will let m=1 and n =5 . So to satisfy both the digraph together we will have to take LCM of (3,5) which is 15

hence m=1 and n=15

edited by

Related questions

13 votes
13 votes
4 answers
1
Arjun asked Aug 12, 2018
4,122 views
Let $R$ be a binary relation on $A = \{a, b, c, d, e, f, g, h\}$ represented by the following two component digraph. Find the smallest integers $m$ and $n$ such that $m <...
25 votes
25 votes
4 answers
2
18 votes
18 votes
5 answers
4
Kathleen asked Sep 25, 2014
9,325 views
Suppose $A$ is a finite set with $n$ elements. The number of elements in the largest equivalence relation of A is$n$$n^2$$1$$n+1$