Discrete Mathematics: Functions, Groups, and Graph Theory

Posted on Jun 19, 2026 in Mathematics

Functions and Mapping Properties

Analysis of the Sine Function

a) Let f:R→Rf:\mathbb{R}\rightarrow\mathbb{R}f:R→R be defined by f(x)=sin⁡xf(x)=\sin xf(x)=sinx.

(i) Image Set and Surjectivity

Given f(x)=sin⁡xf(x)=\sin xf(x)=sinx. For every real number xxx, −1≤sin⁡x≤1-1\leq \sin x\leq 1−1≤sinx≤1.

Hence the image set is f(R)={y:y=sin⁡x,  x∈R}f(\mathbb{R})=\{y:y=\sin x,\;x\in\mathbb{R}\}f(R)={y:y=sinx,x∈R} ={y:−1≤y≤1}=\{y:-1\leq y\leq1\}={y:−1≤y≤1}. f(R)=[−1,1]\boxed{f(\mathbb{R})=[-1,1]}f(R)=[−1,1]. Since the codomain is R\mathbb{R}R but the image set is only [−1,1][-1,1][−1,1], f(R)≠Rf(\mathbb{R})\neq\mathbb{R}f(R)≠R.

Therefore, f is not surjective (onto).\boxed{f \text{ is not surjective (onto).}}f is not surjective (onto).

(ii) Injectivity Analysis

Find {x:x∈R,f(x)=0}\{x:x\in\mathbb{R},f(x)=0\}{x:x∈R,f(x)=0} and conclude whether fff is injective.

Given f(x)=0f(x)=0f(x)=0, then sin⁡x=0\sin x=0sinx=0. This occurs when x=nπ,n∈Zx=n\pi,\quad n\in\mathbb{Z}x=nπ,n∈Z.

Hence, {x:x∈R,f(x)=0}={nπ:n∈Z}\boxed{\{x:x\in\mathbb{R},f(x)=0\}= \{n\pi:n\in\mathbb{Z}\}}{x:x∈R,f(x)=0}={nπ:n∈Z}.

Since different values of xxx have the same image, for example, f(0)=0, f(π)=0f(0)=0,\quad f(\pi)=0f(0)=0,f(π)=0 but 0≠π0\neq \pi0≠π. Therefore, f is not injective (one-one).\boxed{f \text{ is not injective (one-one).}}f is not injective (one-one).

Power Sets and Equivalence Relations

Poset and Elements

(a) Poset P(A),⊆P(A),\subseteqP(A),⊆, where A={a,b,c}A=\{a,b,c\}A={a,b,c}.

P(A)={∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}P(A)=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}P(A)={∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}.

  • Greatest element: {a,b,c}\{a,b,c\}{a,b,c}
  • Least element: ∅\emptyset∅
  • Minimal element: ∅\emptyset∅
  • Maximal element: {a,b,c}\{a,b,c\}{a,b,c}

Inverse of an Equivalence Relation

If RRR is an equivalence relation, prove R−1R^{-1}R−1 is also an equivalence relation. Since RRR is an equivalence relation:

  • Reflexive: (a,a)∈R ⇒ (a,a)∈R−1(a,a)\in R \Rightarrow (a,a)\in R^{-1}(a,a)∈R−1
  • Symmetric: If (a,b)∈R−1(a,b)\in R^{-1}(a,b)∈R−1, then (b,a)∈R(b,a)\in R(b,a)∈R. Since RRR is symmetric, (a,b)∈R(a,b)\in R(a,b)∈R. Hence (b,a)∈R−1(b,a)\in R^{-1}(b,a)∈R−1.
  • Transitive: If (a,b),(b,c)∈R−1(a,b),(b,c)\in R^{-1}(a,b),(b,c)∈R−1, then (b,a),(c,b)∈R(b,a),(c,b)\in R(b,a),(c,b)∈R. Since RRR is transitive, (c,a)∈R(c,a)\in R(c,a)∈R. Therefore, (a,c)∈R−1(a,c)\in R^{-1}(a,c)∈R−1.

Hence R−1R^{-1}R−1 is reflexive, symmetric, and transitive. R−1 is an equivalence relation\boxed{R^{-1}\text{ is an equivalence relation}}R−1 is an equivalence relation.

Definitions of Function Types

Q1 (c)

  • (i) Bijective Function: A function which is both one-one and onto. Example: f:{1,2,3}→{a,b,c}f:\{1,2,3\}\to\{a,b,c\}f:{1,2,3}→{a,b,c} where f(1)=a, f(2)=b, f(3)=cf(1)=a,\;f(2)=b,\;f(3)=cf(1)=a,f(2)=b,f(3)=c.
  • (ii) Many-One Function: Different elements of the domain have the same image. Example: f(1)=a, f(2)=a, f(3)=bf(1)=a,\quad f(2)=a,\quad f(3)=bf(1)=a,f(2)=a,f(3)=b.
  • (iii) Invertible Function: A function having an inverse function. Example: f(x)=x+1f(x)=x+1f(x)=x+1, f−1(x)=x−1f^{-1}(x)=x-1f−1(x)=x−1.
  • (iv) Identity Function: IA(a)=aI_A(a)=aIA​(a)=a for every a∈Aa\in Aa∈A. Example: I(x)=xI(x)=xI(x)=x.

Group Theory: Fourth Roots of Unity

Abelian Group Proof

The fourth roots of unity form an Abelian Group. Set: G={1,−1,i,−i}G=\{1,-1,i,-i\}G={1,-1,i,-i} under multiplication.

  • Closure: Product of any two elements belongs to GGG. Example: i(−i)=1, (−1)i=−ii(-i)=1,\quad (-1)i=-ii(−i)=1,(−1)i=−i.
  • Associativity: Multiplication of complex numbers is associative.
  • Identity: 1.a=a.1=a1.a=a.1=a1.a=a.1=a. Hence the identity is 1.
  • Inverse: 1−1=1, (−1)−1=−11^{-1}=1,\quad (-1)^{-1}=-11−1=1,(−1)−1=−1, i−1=−i, (−i)−1=ii^{-1}=-i,\quad (-i)^{-1}=ii−1=−i,(−i)−1=i.
  • Commutative: ab=baab=baab=ba for all a,b∈Ga,b\in Ga,b∈G.

Hence GGG is an Abelian Group.

Combinatorics and Team Selection

Q4 (b) Team Selection: 4 girls and 7 boys. Total persons = 11.

  • (i) No girls: Choose 5 boys from 7. 7C5=21^7C_5=217C5​=21. \boxed{21}
  • (ii) At least one boy and one girl: Total teams: 11C5=462^{11}C_5=46211C5​=462. All boys: 7C5=21^7C_5=217C5​=21. All girls: impossible (only 4 girls). 462−21=441462-21=441462−21=441. \boxed{441}
  • (iii) At least 3 girls:
    • Exactly 3 girls: 4C3×7C2=4×21=84^4C_3\times ^7C_2 =4\times21=844C3​×7C2​=4×21=84
    • Exactly 4 girls: 4C4×7C1=1×7=7^4C_4\times ^7C_1 =1\times7=74C4​×7C1​=1×7=7
    • Total: 84+7=9184+7=9184+7=91. \boxed{91}

Fundamental Theorems and Principles

Question 4 (a)

  • (i) Abelian Group: A group in which ab=baab=baab=ba for all a,b∈Ga,b\in Ga,b∈G. Example: (Z,+)(\mathbb Z,+)(Z,+).
  • (ii) Pigeonhole Principle: If n+1n+1n+1 objects are placed into nnn boxes, then at least one box contains two or more objects. Example: Among 13 people, at least two have birthdays in the same month.
  • (iii) Isomorphism: Two groups are isomorphic if there exists a one-one and onto homomorphism between them. Example: (Z4,+)≅{1,i,−1,−i}(\mathbb Z_4,+)\cong \{1,i,-1,-i\}(Z4​,+)≅{1,i,-1,-i}.

Graph Theory and Handshaking Theorem

Q5 (a)

(i) Handshaking Theorem

Statement: In any graph, ∑deg⁡(v)=2∣E∣\sum \deg(v)=2|E|∑deg(v)=2∣E∣, where ∣E∣|E|∣E∣ is the number of edges.

Proof: Each edge contributes exactly 2 to the sum of degrees (one at each end vertex). Therefore, ∑deg⁡(v)=2∣E∣\sum \deg(v)=2|E|∑deg(v)=2∣E∣. Hence proved.

(ii) Adjacency Matrix

For a graph with vertices v1,v2,…,vnv_1,v_2,\ldots,v_nv1​,v2​,…,vn​, the adjacency matrix is A=[aij]A=[a_{ij}]A=[aij​] where aij={1,if vi and vj are adjacent0,otherwisea_{ij}= \begin{cases} 1,& \text{if }v_i\text{ and }v_j\text{ are adjacent}\\ 0,& \text{otherwise} \end{cases}aij​={1,0,​if vi​ and vj​ are adjacentotherwise​.

Example:

v1 ---- v2
 \      /
   \  /
    v3

A=[011101110]A= \begin{bmatrix} 0&1&1\\ 1&0&1\\ 1&1&0 \end{bmatrix}A=​011​101​110​​

Graph Classifications and Hamilton Paths

Q5 (b)

  • (i) Directed Graph: A graph whose edges have directions. Example: v1→v2v_1 \rightarrow v_2v1​→v2​.
  • (ii) Connected Graph: A graph in which every pair of vertices is connected by a path.
  • (iii) Complete Graph: A graph in which every vertex is connected to every other vertex. Example: K4K_4K4​ has 4 vertices and 6 edges.
  • (iv) Hamilton Path: A path that visits every vertex exactly once. Example: v1−v2−v3−v4v_1-v_2-v_3-v_4v1​−v2​−v3​−v4​ visits all vertices once.

Visualizing Specific Graph Types

Q5 (c) Draw Graphs

  • (i) K3,4K_{3,4}K3,4​: Bipartite graph with partitions: {u1,u2,u3}\{u_1,u_2,u_3\}{u1​,u2​,u3​} and {v1,v2,v3,v4}\{v_1,v_2,v_3,v_4\}{v1​,v2​,v3​,v4​}. Every uiu_iui​ is connected to every vjv_jvj​.
  • (ii) W6W_6W_6​ (Wheel Graph): A cycle C5C_5C5​ with one central vertex joined to all cycle vertices.
  • (iii) K5K_5K5​: Complete graph with 5 vertices. Number of edges: 5(5−1)2=10\frac{5(5-1)}2=1025(5−1)​=10.
  • (iv) C6C_6C6​: Cycle graph of 6 vertices:
v1—v2
|    |
v6  v3
|    |
v5—v4

Lagrange’s Theorem: Statement and Proof

Statement: If GGG is a finite group and HHH is a subgroup of GGG, then the order of HHH divides the order of GGG. That is, ∣G∣=[G:H]⋅∣H∣|G|=[G:H]\cdot |H|∣G∣=[G:H]⋅∣H∣, where ∣G∣|G|∣G∣ = order of group GGG, ∣H∣|H|∣H∣ = order of subgroup HHH, and [G:H][G:H][G:H] = number of distinct left cosets of HHH in GGG. Hence, ∣H∣ divides ∣G∣\boxed{|H|\; \text{divides}\; |G|}∣H∣divides∣G∣.

Proof: Let HHH be a subgroup of a finite group GGG. Consider all distinct left cosets of HHH in GGG: H,  a1H,  a2H,…,akHH,\; a_1H,\; a_2H,\ldots,a_kHH,a1​H,a2​H,…,ak​H, where k=[G:H]k=[G:H]k=[G:H].

  • Step 1: Each coset has the same number of elements as HHH. Define f:H→aHf:H\rightarrow aHf:H→aH by f(h)=ahf(h)=ahf(h)=ah for every h∈Hh\in Hh∈H. This mapping is one-one and onto. Therefore, ∣aH∣=∣H∣|aH|=|H|∣aH| = ∣H∣.
  • Step 2: Distinct cosets are disjoint. If two cosets aHaHaH and bHbHbH have a common element, then aH=bHaH=bHaH=bH. Hence distinct cosets do not overlap.
  • Step 3: Union of all cosets equals GGG. The distinct left cosets partition the group GGG. Therefore, G=H∪a1H∪a2H∪⋯∪akHG=H\cup a_1H\cup a_2H\cup\cdots\cup a_kHG=H∪a1​H∪a2​H∪⋯∪ak​H. Since the cosets are disjoint, ∣G∣=∣H∣+∣H∣+⋯+∣H∣|G|=|H|+|H|+\cdots+|H|∣G∣=∣H∣+∣H∣+⋯+∣H∣ (kkk times). Thus, ∣G∣=k∣H∣|G|=k|H|∣G∣=k∣H∣ or ∣G∣=[G:H]⋅∣H∣|G|=[G:H]\cdot |H|∣G∣=[G:H]⋅∣H∣.

Hence ∣H∣|H|∣H∣ divides ∣G∣|G|∣G∣. Therefore, ∣H∣∣∣G∣\boxed{|H| \mid |G|}∣H∣∣∣G∣. This proves Lagrange’s Theorem.

Maximum Edges in Simple Graphs

a) For any Simple Graph GGG with nnn vertices, prove that the number of edges is less than or equal to n(n−1)2\frac{n(n-1)}{2}2n(n−1)​.

Proof: In a simple graph, no loops or multiple edges are allowed. Each vertex can be connected to at most n−1n-1n−1 other vertices. Therefore, the maximum possible sum of degrees is n(n−1)n(n-1)n(n−1). By the Handshaking Theorem, ∑deg⁡(v)=2e\sum \deg(v)=2e∑deg(v)=2e, where eee is the number of edges. Hence, 2e≤n(n−1)2e \leq n(n-1)2e≤n(n−1). Dividing both sides by 2, e≤n(n−1)2e \leq \frac{n(n-1)}{2}e≤2n(n−1)​. Therefore, e≤n(n−1)2\boxed{e \leq \frac{n(n-1)}{2}}e≤2n(n−1)​. Hence proved.

Graph Definitions and Examples

Q5 (b) Define Cycle Graph, Bipartite Graph, Path Graph and Star Graph with Example

  • (i) Cycle Graph: A graph in which vertices form a closed path and each vertex has degree 2. Example: C4C_4C4.
  • (ii) Bipartite Graph: A graph whose vertex set can be divided into two disjoint sets V1V_1V1​ and V2V_2V2​ such that every edge joins a vertex of V1V_1V1​ to a vertex of V2V_2V2​. Example: K2,3K_{2,3}K2,3​.
  • (iii) Path Graph: A graph whose vertices are arranged in a single path. Example: P5P_5P5​: v1 —- v2 —- v3 —- v4 —- v5.
  • (iv) Star Graph: A graph having one central vertex connected to all other vertices. Example: S5S_5S5​ where v1v_1v1​ is the central vertex.

Mathematical Induction on Trees

Q5 (c) Prove that if GGG is a Tree with nnn vertices, then it has exactly n−1n-1n−1 edges.

Proof by Mathematical Induction:

  • Base Case: For n=1n=1n=1, a tree consists of a single vertex and no edges. e=0=1−1e=0=1-1e=0=1−1. Thus the result is true.
  • Induction Hypothesis: Assume every tree with kkk vertices has k−1k-1k−1 edges.
  • Induction Step: Consider a tree with k+1k+1k+1 vertices. A tree always contains at least one pendant (leaf) vertex. Remove a leaf vertex and its incident edge. The remaining graph is still a tree with kkk vertices. By the induction hypothesis, the number of edges = k−1. Adding back the removed vertex and edge increases the number of edges by 1. Therefore, e=(k−1)+1=ke=(k-1)+1=ke=(k−1)+1=k. Since the tree has k+1k+1k+1 vertices, e=(k+1)−1e=(k+1)-1e=(k+1)-1. Hence the theorem holds for k+1k+1k+1.

Conclusion: By mathematical induction, A tree with n vertices has exactly n−1 edges\boxed{\text{A tree with } n \text{ vertices has exactly } n-1 \text{ edges}}.