Solution: The procedure for computing the shortest distance/path from a to any vertex G. Initially, let P={a} and T=v-{a}. For every vertex t in T. Let ℓ (t) = w(a, t) Select the vertex in T that has the smallest index with respect to P. Let x denote the vertex. ...

Read More »## Euler’s formula for planner graphs| Discrete Mathematics

Proof: We have to proved V-E+R=2 for any connected planner graph. Where v, e, r are the number of vertices, edges and regions of the graph respectively. The proof proceeds by induction on the number of edges. As the basis of induction we observe that for the two graphs with ...

Read More »## An undirected graph possess an Eulerian path if and only if, is connected and has either zero or two vertices of odd degree.

Proof: Suppose that the graph possess an eulerian path. That the graph must be connected is obvious. When the eulerian path is traced, we observe that every time the path meets a vertex, it goes through two edges which are incident with the vertex and have not been traced before. ...

Read More »## A tree has two vertices of degree 2. One vertex of degree 3 and 3 vertices of degree 4.How many vertices of degree 1 does it have?

Exercise:A tree has 2n vertices of degree 1. 3n vertices of degree 2 and n vertices of degree 3. Determine the number of vertices and edges in the tree. Solution: 2n vertices has total degree = 2n× 1 = 2n 3n ″ ″ ″ ″ = 3n×2 =6n n ″ ...

Read More »## Absorption Property, Idempotent Property| Discrete mathematics

Absorption Property: For any a, b in A, a˅(a˄b) =a and a˄(a˅b)=a Proof: Since a˅(a˄b) is the join of a and (a˄b) then , a˅(a˄b) ≥a ————————-(1) Since a≥a and a≥(a˄b) which implies that (a˅a) ≥ a˅(a˄b) ⇒ a≥ a˅(a˄b) ———————————(2) From (1) and (2) we get, a˅(a˄b)=a Now ...

Read More »## Both the join and meet operations are associative

Both the join and meet operations are associative i.e., a ˅(b˅c) =(a˅b) ˅c and a˄(b˄c)=(a˄b) ˄c Proof: We first show that, the join operation is associative i.e., a ˅(b˅c) =(a˅b) ˅c Let a ˅(b˅c) = g and (a˅b) ˅c=h Since g is the least upper bound of a and (b˅c) ...

Read More »## Show that R is a partially ordering relation.

For a given set A, consider the relation R={(x,y)|x∊P(A), y∊P(A) and x≤y. Show that R is a partially ordering relation. Proof: For all a∊P(A), a≤a ⟹(a,a) ∊R, R is reflexive Let (a,b) ∊R and (b,a) ∊R then a≤b and b≤a implies that a=b. ∴ R is an anti-symmetric. Let (a,b) ...

Read More »## Let R be a reflexive relation on a set A. Show that R is an equivalence relation if and only if (a,b) and (a,c) in R implies that (b,c) ∊R.

Proof: First we say that R is an equivalence relation. We have (a,b)∊R and (a,c) ∊R ⟹(b,a) ∊R and (a,c) ∊R [∵ R is symmetric] ⟹(b,c) ∊R Conversely, we suppose that (b,c) ∊R Given that R is reflexive. Let (a,b) ∊R, then there exist x∊A such that (x,a) ∊R and ...

Read More »## Let R be a transitive reflexive relation on A. Let T be a relation on A such that (a, b) ∊T if and only if both (a, b) ∊ T and (b, a) ∊ R. Show that T is equivalence relation.

Proof: For all a ∊ R, (a, a) ∊ R. Since R is reflexive. So according to problem (a, a) ∊ T. Suppose (a, b) ∊ T. Then by problem (a, b) ∊ R and (b, a) ∊ R ⇒ (b, a) ∊R and (a, b) ∊R ⇒ (b, a)∊ ...

Read More »## Let R be a symmetric and transitive relation on a set. Show that for every a in A there exist b in A such that (a, b) ∊ R then R is an equivalence relation.

Proof: For all a ∊ A, we have (a, b) ∊ R. Since R is symmetric, so (b, a) ∊ R Now, (a, b) ∊ R and (b, a) ∊ R imply that (a, a) ∊ R. Since R is transitive hence R is reflexive. Therefore R is an equivalence ...

Read More »