Math by Tathagata
In this post, we will determine whether the following argument is valid or invalid. Lets consider the following two examples. Question 1: Check whether the argument is valid or not: p∨q, q→r, p→s, ∼s ⇒ r. Answer: We will proceed as follows: 1. p∨q (given) 2. q∨p (commutativity) 3. q→r (given) 4. ∼q∨r (equivalent to … Read more
The Pigeonhole Principle states that if n containers are occupied by more than n items, then at least one container must contain more than one item. In this page we will study Pigeonhole Principle with its statement and examples. Also, learn about the generalised version of pigeonhole principle. Pigeonhole Principle Statement If n containers are … Read more
In graph theory, the degree of a vertex is the number of edges connected to it. In this article, we will study the degree of a vertex in a graph with its definition, examples, and related theorems, such as Handshaking lemma. Degree of a Vertex Definition: In an undirected graph, the number of edges connected … Read more
In this page, we will show that a simple graph with n vertices and k components have at most (n-k)(n-k+1)/2 edges. Question: Prove that a simple graph of $n$ vertices and $k$ components can have at most $\dfrac{(n-k)(n-k+1)}{2}$ number of edges. Answer: Let the $i$-th component of the graph G is denoted by Gi. Suppose … Read more
A tree with n vertices has (n-1) edges. For example, a tree with 5 vertices should have 5-1=4 edges. In this post, we prove that a tree contains (n-1) edges if it has n vertices. A tree of n vertices has n-1 edges Theorem: Show that a tree with n vertices has (n-1) edges. Proof: … Read more
For n≥2, a simple graph with n vertices has a pair of vertices of same degree. In this post, we will prove this theorem on simple graphs. Before we do this, let us first recall a simple graph which is given below. A graph is called a simple graph if there is only one edge … Read more
In this page, you will find practice problems on Discrete Mathematics. Mid Sem Practice Problems Q1: What is tautology, contradiction and contingency? Give examples. Q2: What is a well-formed formula? (Answer: A well-formed formula is an expression consisting of variables, parentheses, and connective symbols. For example, p∨q.) Q2: Define an equivalence relation on a non-empty … Read more