Discrete Mathematics

 Cartesian Product / Cross Product

Example − If we take two sets A={a,b}A={a,b} and B={1,2}B={1,2},

The Cartesian product of A and B is written as − A×B={(a,1),(a,2),(b,1),(b,2)}

The Cartesian product of B and A is written as  B×A={(1,a),(1,b),(2,a),(2,b)}

Power Set

Power set of a set S is the set of all subsets of S including the empty set. The cardinality of a power set of a set S of cardinality n is 2n. Power set is denoted as P(S)P(S).

Example −

For a set S={a,b,c,d}

Hence, P(S)=P(S)=

{{∅},{a},{b},{c},{d},{a,b},{a,c},{a,d},{b,c},{b,d},{c,d},{a,b,c},{a,b,d},{a,c,d},{b,c,d},{a,b,c,d}}

|P(S)|=2pow (4)=16

Note − The power set of an empty set is also an empty set.

Prepositional Logic – Definition

A proposition is a collection of declarative statements that has either a truth value "T” or a truth value "F". A propositional consists of propositional variables and connectives. We denote the propositional variables by capital letters (A, B, etc). The connectives connect the propositional variables.

Some examples of Propositions are given below −

·         "Man is Mortal", it returns truth value “T”

·         "12 + 9 = 3 – 2", it returns truth value “F”

The following is not a Proposition −

·         "A is less than 2". It is because unless we give a specific value of A, we cannot say whether the statement is T or F.

Connectives

In propositional logic generally we use five connectives which are −

·         OR (∨∨)

·         AND (∧∧)

·         Negation/ NOT (¬¬)

·         Implication / if-then (→→)

·         If and only if (⇔⇔).

OR (∨) − The OR operation of two propositions A and B (written as A∨BA∨B) is T if at least any of the propositional variable A or B is T.

The truth table is as follows −

A	B	A ∨ B
T	T	T
T	F	T
F	T	T
F	F	F

AND (∧) − The AND operation of two propositions A and B (written as A∧BA∧B) is T if both the propositional variable A and B is T.

The truth table is as follows −

A	B	A ∧ B
T	T	T
T	F	F
F	T	F
F	F	F

Negation (¬) − The negation of a proposition A (written as ¬A¬A) is F when A is T and is T when A is F.

The truth table is as follows −

A	¬ A
T	F
F	T

Implication / if-then (→) − An implication A→BA→B is the proposition “if A, then B”. It is F if A is T and B is F. The rest cases are T.

The truth table is as follows −

A	B	A → B
T	T	T
T	F	F
F	T	T
F	F	T

If and only if (⇔) − A⇔BA⇔B is bi-conditional logical connective which is T when p and q are same, i.e. both are F or both are T.

The truth table is as follows −

A	B	A ⇔ B
T	T	T
T	F	F
F	T	F
F	F	T

Tautologies

A Tautology is a formula which is always T for every value of its propositional variables.

Example − Prove [(A→B)∧A]→B is a tautology

The truth table is as follows −

A	B	A → B	(A → B) ∧ A	[( A → B ) ∧ A] → B
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

As we can see every value of [(A→B)∧A]→B is "T", it is a tautology.

Contradictions

A Contradiction is a formula which is always F for every value of its propositional variables.

Example − Prove (A∨B)∧[(¬A)∧(¬B)] is a contradiction

The truth table is as follows –

As we can see every value of (A∨B)∧[(¬A)∧(¬B is “F”, it is a contradiction.

Contingency

A Contingency is a formula which has both some T and some F values for every value of its propositional variables.

Example − Prove (A∨B)∧(¬A)a contingency

The truth table is as follows −

A	B	A ∨ B	¬ A	(A ∨ B) ∧ (¬ A)
T	T	T	F	F
T	F	T	F	F
F	T	T	T	T
F	F	F	T	F

As we can see every value of (A∨B)∧(¬A)has both “T” and “F”, it is a contingency.

Propositional Equivalences

Two statements X and Y are logically equivalent if any of the following two conditions hold −

·         The truth tables of each statement have the same truth values.

·         The bi-conditional statement X⇔YX⇔Y is a tautology.

Example − Prove ¬(A∨B)and[(¬A)∧(¬B)] are equivalent

Testing by 1^st method (Matching truth table)

Here, we can see the truth values of ¬(A∨B)and[(¬A)∧(¬B)] are same, hence the statements are equivalent.

Testing by 2^nd method (Bi-conditionality)

As [¬(A∨B)]⇔[(¬A)∧(¬B)] is a tautology, the statements are equivalent.

Inverse, Converse, and Contra-positive

Implication / if-then (→)(→) is also called a conditional statement. It has two parts −

·         Hypothesis, p

·         Conclusion, q

As mentioned earlier, it is denoted as p→q.

Example of Conditional Statement − “If you do your homework, you will not be punished.” Here, "you do your homework" is the hypothesis, p, and "you will not be punished" is the conclusion, q.

Inverse − An inverse of the conditional statement is the negation of both the hypothesis and the conclusion. If the statement is “If p, then q”, the inverse will be “If not p, then not q”. Thus the inverse of p→q is ¬p→¬q.

Example − The inverse of “If you do your homework, you will not be punished” is “If you do not do your homework, you will be punished.”

Converse − The converse of the conditional statement is computed by interchanging the hypothesis and the conclusion. If the statement is “If p, then q”, the converse will be “If q, then p”. The converse of p→q is q→p.

Example − The converse of "If you do your homework, you will not be punished" is "If you will not be punished, you do your homework”.

Contra-positive − The contra-positive of the conditional is computed by interchanging the hypothesis and the conclusion of the inverse statement. If the statement is “If p, then q”, the contra-positive will be “If not q, then not p”. The contra-positive of p→q is ¬q→¬p.

Example − The Contra-positive of " If you do your homework, you will not be punished” is "If you are punished, you did not do your homework”.

Duality Principle

Duality principle states that for any T statement, the dual statement obtained by interchanging unions into intersections (and vice versa) and interchanging Universal set into Null set (and vice versa) is also T. If dual of any statement is the statement itself, it is said self-dual statement.

Example − The dual of (A∩B)∪C(A∩B)∪C is (A∪B)∩C(A∪B)∩C

Normal Forms

We can convert any proposition in two normal forms −

·         Conjunctive normal form

·         Disjunctive normal form

Conjunctive Normal Form

A compound statement is in conjunctive normal form if it is obtained by operating AND among variables (negation of variables included) connected with ORs. In terms of set operations, it is a compound statement obtained by Intersection among variables connected with Unions.

Examples

·         (A∨B)∧(A∨C)∧(B∨C∨D)

·         (P∪Q)∩(Q∪R)

Disjunctive Normal Form    

A compound statement is in conjunctive normal form if it is obtained by operating OR among variables (negation of variables included) connected with ANDs. In terms of set operations, it is a compound statement obtained by Union among variables connected with Intersections.

Examples

·         (A∧B)∨(A∧C)∨(B∧C∧D)

·         (P∩Q)∪(Q∩R)

 

Predicate Logic – Definition

A predicate is an expression of one or more variables defined on some specific domain. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable.

The following are some examples of predicates −

• Let E(x, y) denote "x = y"
• Let X(a, b, c) denote "a + b + c = 0"
• Let M(x, y) denote "x is married to y"

Well Formed Formula

Well Formed Formula (wff) is a predicate holding any of the following −

·        All propositional constants and propositional variables are wffs

·        If x is a variable and Y is a wff, ∀xY and ∃xY are also wff

·        Truth value and false values are wffs

·        Each atomic formula is a wff

·        All connectives connecting wffs are wffs

Quantifiers

The variable of predicates is quantified by quantifiers. There are two types of quantifier in predicate logic − Universal Quantifier and Existential Quantifier.

Universal Quantifier

Universal quantifier states that the statements within its scope are true for every value of the specific variable. It is denoted by the symbol ∀.

∀xP(x) is read as for every value of x, P(x) is true.

Example − "Man is mortal" can be transformed into the propositional form ∀xP(x) where P(x) is the predicate which denotes x is mortal and the universe of discourse is all men.

Existential Quantifier

Existential quantifier states that the statements within its scope are true for some values of the specific variable. It is denoted by the symbol ∃.

∃xP(x) is read as for some values of x, P(x) is true.

Example − "Some people are dishonest" can be transformed into the propositional form ∃xP(x)∃xP(x) where P(x) is the predicate which denotes x is dishonest and the universe of discourse is some people.

Nested Quantifiers

If we use a quantifier that appears within the scope of another quantifier, it is called nested quantifier.

Example

·        ∀ a∃bP(x,y) where P(a,b) denotes a+b=0

·        ∀ a∀b∀cP(a,b,c)where P(a,b)denotes a+(b+c)=(a+b)+c

Note − ∀a∃bP(x,y)≠∃a∀bP(x,y)

Recurrence relation

The procedure for finding the terms of a sequence in a recursive manner is called recurrence relation. We study the theory of linear recurrence relations and their solutions. Finally, we introduce generating functions for solving recurrence relations.

Definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing FnFn as some combination of FiFi with i<ni<n).

Example − Fibonacci series − Fn=Fn−1+Fn−2, Tower of Hanoi − Fn=2Fn−1+1

Linear Recurrence Relations

A linear recurrence equation of degree k or order k is a recurrence equation which is in the format xn=A1xn−1+A2xn−1+A3xn−1+…Akxn−kxn=A1xn−1+A2xn−1+A3xn−1+…Akxn−k(AnAn is a constant and Ak≠0Ak≠0) on a sequence of numbers as a first-degree polynomial.

These are some examples of linear recurrence equations −

Recurrence relations	Initial values	Solutions
Fn = Fn-1 + Fn-2	a1 = a2 = 1	Fibonacci number
Fn = Fn-1 + Fn-2	a1 = 1, a2 = 3	Lucas Number
Fn = Fn-2 + Fn-3	a1 = a2 = a3 = 1	Padovan sequence
Fn = 2Fn-1 + Fn-2	a1 = 0, a2 = 1	Pell number

How to solve linear recurrence relation

Suppose, a two ordered linear recurrence relation is − Fn=AFn−1+BFn−2Fn=AFn−1+BFn−2 where A and B are real numbers.

The characteristic equation for the above recurrence relation is −

x2−Ax−B=0x2−Ax−B=0

Three cases may occur while finding the roots −

Case 1 − If this equation factors as (x−x1)(x−x1)=0(x−x1)(x−x1)=0 and it produces two distinct real roots x1x1 and x2x2, then Fn=axn1+bxn2Fn=ax1n+bx2n is the solution. [Here, a and b are constants]

Case 2 − If this equation factors as (x−x1)2=0(x−x1)2=0 and it produces single real root x1, then Fn=axn1+bnxn1 is the solution.

Case 3 − If the equation produces two distinct complex roots, x1x1 and x2x2 in polar form x1=r∠θx1=r∠θ and x2=r∠(−θ)

then Fn=rn(acos(nθ)+bsin(nθ)) is the solution.

Problem 1

Solve the recurrence Fn=5Fn−1−6Fn−2 where
F0=1 and F1=4

Solution

The characteristic equation of the recurrence relation is −

x2−5x+6=0,

So, (x−3)(x−2)=0

Hence, the roots are −

x1=3and x2=2

The roots are real and distinct. So, this is in the form of case 1

Hence, the solution is −

Fn=axn1+bxn2

Here, Fn=a3n+b2n (As x1=3 and x2=2)Fn=a3n+b2n (As x1=3 and x2=2)

Therefore,

1=F0=a30+b20=a+b1=F0=a30+b20=a+b

4=F1=a31+b21=3a+2b4=F1=a31+b21=3a+2b

Solving these two equations, we get a=2a=2 and b=−1b=−1

Hence, the final solution is −

Fn=2.3n+(−1).2n=2.3n−2nFn=2.3n+(−1).2n=2.3n−2n

Generating Functions represents sequences where each term of a sequence is expressed as a coefficient of a variable x in a formal power series.

Mathematically, for an infinite sequence, say a0,a1,a2,…,ak,…, the generating function will be −

Gx=a0+a1x+a2x2+⋯+akxk+⋯=∑k=0∞akxk

Some Areas of Application

Generating functions can be used for the following purposes −

·        For solving a variety of counting problems. For example, the number of ways to make change for a Rs. 100 note with the notes of denominations Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 and Rs.50

·        For solving recurrence relations

·        For proving some of the combinatorial identities

·        For finding asymptotic formulae for terms of sequences

Relation and thir use

Basic properties: Let R be a binary relation on a set A. 1.      R is reflexive, iff for all x Î A, (x,x) Î R, i.e. xRx is true.       2. R is symmetric, iff for all x, y Î A, if (x, y) Î R, then (y, x) Î R i.e xRy → yRx is true        3. R is transitive iff for all x, y, z Î A, if (x, y) Î R and (y,z) Î R , then (x, z) Î R i.e. (xRy L yRz) → xRz is true A.    Reflexive relations 1.      (1).Definition Let R be a binary relation on a set A. R is reflexive, iff for all x Î A, (x,x) Î R, i.e. xRx is true. Examples: a.       1. Equality is a reflexive relation for any object x,  x = x is true. b.      2. "less then" is not a reflexive relation. It is irreflexive. for any number x, x < x is not true c.       3. " less then or equal to" is a reflexive relation for any number x,  x £ x is true d.      4. A = {1,2,3,4}, R = {(1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (4,4)} e.       5. A = {1,2,3,4}, R = {(1,2), (2,3), (3,4), (4,1)} - not reflexive (it is irreflexive) f.       6. A = {1,2,3,4}, R = {(1,1), (1,2), (3,4), (4,4)} - not reflexive (it is neither reflexive nor irreflexive) 2.      (2). Graph representation of reflexive relations Rule: if xRx is true, there is a loop on node x. Example: A:= {1,2,3} R = "less then or equal to" R = {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)} 3.      (3).Matrix representation of reflexive relations The relation R in the above example would be represented thus:      1  2  3 1  1  0  0 2  0  1  0 3  0  0  1 There are 1's on the diagonal 4.      (4). Reflexive and irreflexive relations Compare the three examples below: 1.                  A = {1,2,3,4}, R1 = {(1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (4,4)} 2.      A = {1,2,3,4}, R2 = {(1,2), (2,3), (3,4), (4,1)} 3.      A = {1,2,3,4}, R3= {(1,1), (1,2), (3,4), (4,4)} R1 is a reflexive relation. R2 ? R3 ? Definition: Let R be a binary relation on a set A. R is irreflexive iff for all x Î A, (x,x) Ï R Definition: Let R be a binary relation on a set A. R is neither reflexive, nor irreflexive iff  there is x Î A, such that (x, x) Î R, and there is y Î A such that (y, y) Ï R Thus R2 is irreflexive, while R3 is neither reflexive nor irreflexive. Summary §  reflexive: for all x: xRx §  irreflexive: for no x: xRx §  neither: for some x: xRx is true, for some y: yRy is false                         Symmetric relations                         (1).Definition R is symmetric, iff for all x, y Î A, if (x, y) Î R, then (y, x) Î R,  i.e xRy → yRx is true This means: if two elements x and y are in relation R, then y and x are also in R,  i.e. if xRy is true, yRx is also true. Examples:  .        1. equality is a symmetric relation: if a = b then b = a a.       2. "less than" is not a symmetric relation, it is anti-symmetric. b.      3. "sister" on the set of females is symmetric. c.       4. "sister" on the set of all human beings is not symmetric. (It is neither symmetric nor anti-symmetric) d.      5. "friends" is symmetric: friend(a,b) → friend(b,a) e.       6. A = {1,2,3,4}, R1 = {(1,1), (1,2), (2,1), (2,3), (3,2), (4,4)} The relation is symmetric. f.       7. A = {1,2,3,4}, R2 = {(1,1), (1,2), (2,3), (4,4)} - not symmetric (it is anti-symmetric) g.      8. A = {1,2,3,4}, R3 = {(1,1), (1,2), (2,1) , (2,3), (4,4)} - not symmetric (it is neither symmetric nor anti-symmetric)                         (2). Graph representation of symmetric relations Rule: if R is a symmetric relation, all links are bi-directional. Example: friend(x,y), x,y Î {Ann, Tim, Paul, Jane, Jim}                         (3). Matrix representation of symmetric relations          Ann   Tim    Paul   Jane   Jim Ann     0     1      0      0      0 Tim     1     0      1      0      0 Paul    0     1      0      0      0 Jane    0     0      0      0      1 Jim     0     0      0      1      0 The matrix is symmetric.                         (4). Symmetric and anti-symmetric relations Compare the relations: 0.      A = {1,2,3,4}, R1 = {(1,1), (1,2), (2,1), (2,3), (3,2), (4,4)} 1.      A = {1,2,3,4}, R2 = {(1,1), (1,2), (2,3), (4,4)} 2.      A = {1,2,3,4}, R3 = {(1,1), (1,2), (2,1) , (2,3), (4,4)} Definition: Let R be a binary relation on a set A. R is anti-symmetric if for all x, y Î A, x ¹ y, (x, y) Î R → (y, x) Ï R. i.e. for all pairs (x,y) in R, x ¹ y, the pair (y,x) is not in R. Definition: R is neither symmetric nor anti-symmetric iff it is not symmetric and not anti-symmetric. Summary §  symmetric: xRy → yRx for all x and y §  anti-symmetric: xRy and yRx → x = y §  neither: for some x and y both xRy and yRx are true,  for others xRy is true, yRx is not true.                         Transitive relations                         (1). Definition Let R be a binary relation on a set A. R is transitive iff for all x, y, z Î A, if (x, y) Î R and (y,z) Î R , then (x, z) Î R i.e. (xRy L yRz) → xRz is true Examples:  .        1. Equality is a transitive relation: a = b, b = c, hence a = c a.       2. "less than" is a transitive relation: a < b, b < c, hence a < c b.      3. mother(x,y) is not a transitive relation c.       4. sister(x,y) is a transitive relation d.      5. brother (x,y) is a transitive relation e.       6. A = {1,2,3,4} R = {(1,1), (1,2), (1,3), (2,3), (4,3)} - transitive f.       7. A = {1,2,3,4} R = {(1,1), (1,2), (1,3), (2,3), (3,4)} - not transitive                         (2). Graph representation of transitive relations Rule: if there is a link from a to b, and a link from b to c,  then there must be a link from a to c. Example: A = {1,2,3,4} R = {(1,2), (1,3), (1,4),(2,3),(2,4),(3,4)} This is the relation "less than"   Learning Goals Given a relation be able to determine its properties: a.       is the relation reflexive, irreflexive, or neither reflexive nor irreflexive b.      is the relation symmetric, anti-symmetric, or neither symmetric nor anti-symmetric c.       is the relation transitive or not. Exam-like problems 1.      For each of the following relations determine whether it is reflexive, irreflexive, neither symmetric, anti-symmetric, neither transitive, not transitive All relations are on the set of humans R1 = {(x,y) | x is a child of y} R2 = {(x,y) | x is a descendent of y} R3 = {(x,y) | x is a spouse of y} R4 = {(x,y) | x is a wife of y} R5 = {(x,y) | x and y have same parents} R6 = {(x,y) | x and y have same parent} R7 = {(x,y) | x is younger than y } 2.      Name (or specify) a relations that is: transitive symmetric reflexive irreflexive anti-symmetric

What is a Graph?

Definition − A graph (denoted as G=(V,E)G=(V,E)) consists of a non-empty set of vertices or nodes V and a set of edges E.

Example − Let us consider, a Graph is G=(V,E)G=(V,E) 

where V={a,b,c,d}V={a,b,c,d} and E={{a,b},{a,c},{b,c},{c,d}}E={{a,b},{a,c},{b,c},{c,d}}

Degree of a Vertex − The degree of a vertex V of a graph G (denoted by deg (V)) is the number of edges incident with the vertex V.

Vertex	Degree	Even / Odd
a	2	even
b	2	even
c	3	odd
d	1	odd

Even and Odd Vertex − If the degree of a vertex is even, the vertex is called an even vertex and if the degree of a vertex is odd, the vertex is called an odd vertex.

Degree of a Graph − The degree of a graph is the largest vertex degree of that graph. For the above graph the degree of the graph is 3.

The Handshaking Lemma − In a graph, the sum of all the degrees of all the vertices is equal to twice the number of edges.

Types of Graphs

There are different types of graphs, which we will learn in the following section.

Null Graph

A null graph has no edges. The null graph of nn vertices is denoted by NnNn

Simple Graph

A graph is called simple graph/strict graph if the graph is undirected and does not contain any loops or multiple edges.

Multi-Graph

If in a graph multiple edges between the same set of vertices are allowed, it is called Multigraph. In other words, it is a graph having at least one loop or multiple edges.

Directed and Undirected Graph

A graph G=(V,E)G=(V,E) is called a directed graph if the edge set is made of ordered vertex pair and a graph is called undirected if the edge set is made of unordered vertex pair.

Connected and Disconnected Graph

A graph is connected if any two vertices of the graph are connected by a path; while a graph is disconnected if at least two vertices of the graph are not connected by a path. If a graph G is disconnected, then every maximal connected subgraph of GGis called a connected component of the graph GG.

Regular Graph

A graph is regular if all the vertices of the graph have the same degree. In a regular graph G of degree rr, the degree of each vertex of GG is r.

Complete Graph

A graph is called complete graph if every two vertices pair are joined by exactly one edge. The complete graph with n vertices is denoted by KnKn

Cycle Graph

If a graph consists of a single cycle, it is called cycle graph. The cycle graph with n vertices is denoted by CnCn

Bipartite Graph

If the vertex-set of a graph G can be split into two disjoint sets, V1V1 and V2V2, in such a way that each edge in the graph joins a vertex in V1V1 to a vertex in V2V2, and there are no edges in G that connect two vertices in V1V1 or two vertices in V2V2, then the graph GG is called a bipartite graph.

Complete Bipartite Graph

A complete bipartite graph is a bipartite graph in which each vertex in the first set is joined to every single vertex in the second set. The complete bipartite graph is denoted by Kx,yKx,ywhere the graph GG contains xx vertices in the first set and yyvertices in the second set.

Planar vs. Non-planar graph

Planar graph − A graph GG is called a planar graph if it can be drawn in a plane without any edges crossed. If we draw graph in the plane without edge crossing, it is called embedding the graph in the plane.

Non-planar graph − A graph is non-planar if it cannot be drawn in a plane without graph edges crossing.

Isomorphism

If two graphs G and H contain the same number of vertices connected in the same way, they are called isomorphic graphs (denoted by G≅HG≅H).

It is easier to check non-isomorphism than isomorphism. If any of these following conditions occurs, then two graphs are non-isomorphic −

• The number of connected components are different
• Vertex-set cardinalities are different
• Edge-set cardinalities are different
• Degree sequences are different

Example

The following graphs are isomorphic −

Homomorphism

A homomorphism from a graph GG to a graph HH is a mapping (May not be a bijective mapping)h:G→Hh:G→H such that − (x,y)∈E(G)→(h(x),h(y))∈E(H)(x,y)∈E(G)→(h(x),h(y))∈E(H). It maps adjacent vertices of graph GG to the adjacent vertices of the graph HH.

Properties of Homomorphisms

·        A homomorphism is an isomorphism if it is a bijective mapping.

·        Homomorphism always preserves edges and connectedness of a graph.

·        The compositions of homomorphisms are also homomorphisms.

·        To find out if there exists any homomorphic graph of another graph is a NPcomplete problem.

Euler Graphs

A connected graph GG is called an Euler graph, if there is a closed trail which includes every edge of the graph GG. An Euler path is a path that uses every edge of a graph exactly once. An Euler path starts and ends at different vertices.

An Euler circuit is a circuit that uses every edge of a graph exactly once. An Euler circuit always starts and ends at the same vertex. A connected graph GG is an Euler graph if and only if all vertices of GG are of even degree, and a connected graph GG is Eulerian if and only if its edge set can be decomposed into cycles.

The above graph is an Euler graph as “a1b2c3d4e5c6f7g”“a1b2c3d4e5c6f7g” covers all the edges of the graph.

Hamiltonian Graphs

A connected graph GG is called Hamiltonian graph if there is a cycle which includes every vertex of GG and the cycle is called Hamiltonian cycle. Hamiltonian walk in graph GG is a walk that passes through each vertex exactly once.

If GG is a simple graph with n vertices, where n≥3n≥3 If deg(v)≥n2deg(v)≥n2 for each vertex vv, then the graph GG is Hamiltonian graph. This is called Dirac's Theorem.

If GG is a simple graph with nn vertices, where n≥2n≥2 if deg(x)+deg(y)≥ndeg(x)+deg(y)≥n for each pair of non-adjacent vertices x and y, then the graph GG is Hamiltonian graph. This is called Ore's theorem.

What is Tree and Forest?

Tree

o    In graph theory, a tree is an undirected, connected and acyclic graph. In other words, a connected graph that does not contain even a single cycle is called a tree.

o    A tree represents hierarchical structure in a graphical form.

o    The elements of trees are called their nodes and the edges of the tree are called branches.

o    A tree with n vertices has (n-1) edges.

o    Trees provide many useful applications as simple as a family tree to as complex as trees in data structures of computer science.

o    A leaf in a tree is a vertex of degree 1 or any vertex having no children is called a leaf.

  b Example

In the above example, all are trees with fewer than 6 vertices.

Forest

In graph theory, a forest is an undirected, disconnected, acyclic graph. In other words, a disjoint collection of trees is known as forest. Each component of a forest is tree.

Example

The above graph looks like a two sub-graphs but it is a single disconnected graph. There are no cycles in the above graph. Therefore it is a forest.

2. Properties of Trees

1.      Every tree which has at least two vertices should have at least two leaves.

2.      Trees have many characterizations:
Let T be a graph with n vertices, then the following statements are equivalent:

o    T is a tree.

o    T contains no cycles and has n-1 edges.

o    T is connected and has (n -1) edge.

o    T is connected graph, and every edge is a cut-edge.

o    Any two vertices of graph T are connected by exactly one path.

o    T contains no cycles, and for any new edge e, the graph T+ e has exactly one cycle.

3.      Every edge of a tree is cut -edge.

4.      Adding one edge to a tree defines exactly one cycle.

5.      Every connected graph contains a spanning tree.

6.      Every tree has at least two vertices of degree two.

Draw a weighted graph given adjacency matrix?  [BUET M.SC Admission -2015]

pigeonhole principle(6 numbers,show at least 2 of them having same remainder after dividing 5)  [BUET M.SC Admission -2015]

The Pigeonhole Principle

Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost. Because there are 20 pigeons but only 19 pigeonholes, a least one of these 19 pigeonholes must have at least two
pigeons in it. To see why this is true, note that if each pigeonhole had at most one pigeon in it, at most 19 pigeons, one per hole, could be accommodated. This illustrates a general principle called the pigeonhole principle, which states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it.

Theorem –

I) If “A” is the average number of pigeons per hole, where A is not an integer then

§  At least one pigeon hole contains ceil[A] (smallest integer greater than or equal to A) pigeons

§  Remaining pigeon holes contains at most floor[A] (largest integer less than or equal to A) pigeons