EMTH403

Mathematical Foundation
for Computer Science
Complete Study Guide

14 Units Covered Key Definitions Important Formulas

Hidden Connections Exam Tips Visual Summaries

Lovely Professional University · Dr. Kulwinder Singh (Ed.)

EMTH403 · Mathematical Foundation for Computer Science Study Guide

Table of Contents
The Foundations: Logic & Proofs
Unit 1
Propositions, Connectives, Truth Tables, Implications

Variables & Quantifiers

Unit 2
Predicates, Universal & Existential Quantifiers, Negation

Partially Ordered Sets (Posets)

Unit 3
Relations, Hasse Diagrams, Lattices, Zorn's Lemma

Boolean Algebra
Unit 4
Laws, Gates, Simplification, Karnaugh Maps

Counting Principles
Unit 5
Product/Sum Rules, Permutations, Combinations, Pigeonhole

Graph Terminology
Unit 6-7
Vertices, Edges, Types of Graphs, Isomorphism, Planar Graphs

Connectivity
Unit 8
Paths, Circuits, Cut Vertices, Bridges, Components

Euler & Hamilton Paths

Unit 9
Königsberg, Euler Circuits, Hamiltonian Cycles, Ore's Theorem

Shortest-Path Problems
Unit 10
Dijkstra's Algorithm, Bellman-Ford, Weighted Graphs

Graph Coloring
Unit 11
Chromatic Number, 4-Color Theorem, Scheduling Applications

Trees
Unit 12
Properties, Binary Trees, Balanced Trees, Applications

Spanning Trees
Unit 13
Prim's, Kruskal's, Backtracking, DFS/BFS Trees

Tree Traversal
Unit 14
Preorder, Inorder, Postorder, Expression Trees

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 2

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 1 The Foundations: Logic & Proofs

Building the language of mathematics

1.1 What is a Proposition?

A proposition is a declarative sentence that is either TRUE or FALSE, but not both. This binary nature is the
foundation of all digital computing — every bit in a computer is a proposition with value 0 (False) or 1 (True).

KEY DEFINITION

Proposition: A declarative sentence with a definite truth value (T or F). Questions, commands, and paradoxes are
NOT propositions.

1.2 Logical Connectives

Name Symbol Meaning True when…

Negation ¬p NOT p p is False

Conjunction p∧q p AND q Both p and q are True

Disjunction p∨q p OR q At least one is True

Implication p→q If p then q p is False OR q is True

Biconditional p↔q p if and only if q p and q have same truth value

XOR p⊕q Exclusive OR Exactly one is True

■ The implication p → q is FALSE only when p is TRUE and q is FALSE. This is the most commonly
misunderstood connective!

1.3 Conditional Statement Family

Form Expression Example (p: 'It rains', q: 'Ground is wet')

Conditional p→q If it rains, the ground is wet

Converse q→p If the ground is wet, it rained

Inverse ¬p → ¬q If it doesn't rain, the ground is not wet

Contrapositive ¬q → ¬p If the ground is not wet, it didn't rain

■ The CONTRAPOSITIVE is logically equivalent to the original conditional. The CONVERSE and INVERSE
are equivalent to EACH OTHER, but NOT to the original.

■ Connection to CS: Conditional logic directly maps to IF-THEN statements in every programming language. Proof by
contrapositive is a key technique in algorithm correctness proofs.

1.4 Logical Equivalences (Laws)

Law Expression

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 3

EMTH403 · Mathematical Foundation for Computer Science Study Guide

Double Negation ¬(¬p) ≡ p

De Morgan #1 ¬(p ∧ q) ≡ ¬p ∨ ¬q

De Morgan #2 ¬(p ∨ q) ≡ ¬p ∧ ¬q

Absorption p ∨ (p ∧ q) ≡ p

Idempotent p∧p≡p|p∨p≡p

Distributive p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 4

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 2 Variables & Quantifiers

Making statements about all or some elements of a domain

2.1 Predicates vs Propositions

A predicate (propositional function) P(x) is a statement that becomes a proposition when a specific value is
substituted for the variable x. The domain (universe of discourse) determines the valid values.

KEY DISTINCTION

P(x) alone is NOT a proposition — it has no truth value. P(3) with a specific value substituted IS a proposition.

2.2 The Two Quantifiers

Quantifier Symbol Meaning Is True when… Is False when…

Universal ∀x P(x) For ALL x, P(x) P(x) is true for There exists an x
every x where P(x) is false

Existential ∃x P(x) There EXISTS an x P(x) is true for at P(x) is false for all x
least one x

2.3 Negating Quantifiers (De Morgan for Quantifiers)

¬(∀x P(x)) ≡ ∃x ¬P(x) [Not all → There exists one that isn't]

¬(∃x P(x)) ≡ ∀x ¬P(x) [None exists → All are not]

■ To disprove a universal statement, you only need ONE counterexample. To disprove an existential statement,
you must show it fails for ALL elements.

■ Connection: Quantifiers are the foundation of database queries. SQL's 'EXISTS' and 'ALL' are direct implementations of
∃ and ∀.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 5

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 3 Partially Ordered Sets (Posets)

Ordering elements that may not always be comparable

3.1 Relations and Partial Orders

A relation R on a set S is a partial order if it satisfies three properties. A set S with a partial order ≤ is called a
poset, written (S, ≤).

Property Meaning Example (≤ on integers)

Reflexive a ≤ a for all a in S 5≤5✓

Antisymmetric If a ≤ b AND b ≤ a, then a = b If 3 ≤ 3 and 3 ≤ 3 then 3 = 3 ✓

Transitive If a ≤ b AND b ≤ c, then a ≤ c If 2 ≤ 3 and 3 ≤ 5 then 2 ≤ 5 ✓

3.2 Hasse Diagrams

A Hasse diagram is a simplified visual representation of a poset. Rules: (1) Place higher elements above lower
ones. (2) Draw a line between a and b if a < b and no c exists with a < c < b (i.e., b covers a). (3) Omit arrows and
self-loops.

■ In a Hasse diagram: the MAXIMAL element has nothing above it; the MINIMAL element has nothing below it. A
GREATEST element is above ALL others; a LEAST element is below ALL others.

3.3 Lattices
A poset is a lattice if every pair of elements has both a least upper bound (join, ∨) and a greatest lower bound
(meet, ∧).

■ Connection: File system directories form a poset. Boolean algebra is a special lattice. Lattices underpin type
hierarchies in object-oriented programming.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 6

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 4 Boolean Algebra

The mathematics behind digital circuits

4.1 Core Laws of Boolean Algebra

Law AND form OR form

Identity x·1=x x+0=x

Null x·0=0 x+1=1

Idempotent x·x=x x+x=x

Complement x · x' = 0 x + x' = 1

Commutative x·y=y·x x+y=y+x

Associative (x·y)·z = x·(y·z) (x+y)+z = x+(y+z)

Distributive x·(y+z) = x·y + x·z x+(y·z) = (x+y)·(x+z)

De Morgan (x·y)' = x' + y' (x+y)' = x' · y'

Double Complement (x')' = x (x')' = x

Absorption x·(x+y) = x x + x·y = x

■ De Morgan's Laws are the KEY to simplifying Boolean expressions: to negate a product, sum the negations; to
negate a sum, multiply the negations.

4.2 Logic Gates

Gate Symbol Expression Output

AND · A·B 1 only when both A=1

and B=1

OR + A+B 1 when at least one input

is 1

NOT ' A' Inverts the input

NAND (·)' (A·B)' NOT AND — universal

gate

NOR (+)' (A+B)' NOT OR — universal

gate

XOR ⊕ A⊕B 1 when inputs differ

■ Connection: NAND and NOR are called UNIVERSAL GATES because any logic circuit can be built using only NAND
(or only NOR) gates. This is why they are preferred in chip manufacturing.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 7

EMTH403 · Mathematical Foundation for Computer Science Study Guide

■ To simplify Boolean expressions: (1) Apply De Morgan's Laws, (2) Use Absorption, (3) Factor out
common terms, (4) Check with a truth table for small expressions.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 8

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 5 Basic Counting Principles

Permutations, combinations, and combinatorial reasoning

5.1 The Four Fundamental Rules

Rule Condition Formula Example

Product Rule Tasks done sequentially/i n1 × n2 × … 3 shirts × 4 pants = 12

ndependently outfits

Sum Rule Mutually exclusive n1 + n2 + … 3 cats or 4 dogs = 7 pets

choices to choose from

Subtraction Inclusion-Exclusion |A∪B| = |A|+|B|−|A∩B| Password ≥8 chars, not

starting with 0

Division Rule Equivalent arrangements n/d Arranging n people in a

circle: (n−1)!

5.2 Permutations vs Combinations

Permutation P(n,r) = n! / (n−r)! [Order MATTERS]

Combination C(n,r) = n! / [r!(n−r)!] [Order does NOT matter]

■ MNEMONIC: 'Permutation' contains the word 'arrange' in spirit — order matters like placing trophies.
'Combination' is like a combination LOCK — same numbers, different order still opens it. Wait — actually
combinations DON'T care about order. It's just a historical misnaming!

5.3 Pigeonhole Principle

If n+1 or more objects are placed into n boxes, then at least one box contains 2 or more objects. The generalized
version: if N objects go into k boxes, at least one box has ■N/k■ objects.

■ Pigeonhole applications: In any group of 367 people, at least 2 share a birthday. In any sequence of n²+1
distinct numbers, there is an increasing or decreasing subsequence of length n+1.

■ Connection: Pigeonhole Principle is used in computer science to prove that perfect hashing is impossible for arbitrary
inputs, and in cryptography to show collision existence.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 9

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNITS 6–7 Graph Terminology

The universal language for modelling networks, maps, and relationships

6.1 What is a Graph?

A graph G = (V, E) consists of a set V of vertices (nodes) and a set E of edges (links). Edges connect pairs of
vertices. Graphs model roads, networks, social connections, chemical bonds, and much more.

Graph Type Description Example

Simple graph No self-loops, no multiple edges Friend network

Multigraph Multiple edges between same pair Parallel roads

allowed

Pseudograph Loops allowed Circuit with feedback

Directed graph Edges have direction (digraph) Web links, one-way streets

Weighted graph Edges have numerical weights Road maps with distances

Bipartite graph Vertices split into 2 sets; edges only Job-applicant matching
cross

Complete graph Kn Every vertex connected to every Round-robin tournament

other

6.2 Key Terminology at a Glance

• Degree deg(v): number of edges incident to vertex v
• Handshaking Theorem: Sum of all degrees = 2|E| (every edge contributes 2)
• Isolated vertex: degree 0 | Pendant vertex: degree 1
• Adjacency: two vertices are adjacent if connected by an edge
• Subgraph: graph formed by a subset of V and E
• Complement G': same vertices, but edges are exactly those NOT in G

■ HANDSHAKING THEOREM: The sum of all vertex degrees equals TWICE the number of edges. Consequence:
In any graph, the number of vertices with ODD degree is always EVEN.

6.3 Planar Graphs & Euler's Formula

Euler's Formula: V − E + F = 2 (V=vertices, E=edges, F=faces including outer)

Planar condition: E ≤ 3V − 6 (for simple connected planar graphs with V ≥ 3)

■ K5 (5 vertices, all connected) and K3,3 (bipartite, 3+3 vertices) are the two fundamental NON-PLANAR
graphs. By Kuratowski's theorem, a graph is non-planar iff it contains a subdivision of K5 or K3,3.

6.4 Graph Isomorphism

Two graphs are isomorphic if there is a bijection between their vertex sets that preserves adjacency. Isomorphic
graphs look different but are structurally identical.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 10

EMTH403 · Mathematical Foundation for Computer Science Study Guide

■ Quick isomorphism checks: (1) Same number of vertices, (2) Same number of edges, (3) Same degree
sequence (sorted list of degrees). If any differ → NOT isomorphic.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 11

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 8 Connectivity
Paths, circuits, and how graphs hold together

8.1 Paths and Circuits

Term Definition

Walk Sequence of vertices where consecutive ones are adjacent (edges/vertices can repeat)

Path A walk with NO repeated vertices

Simple path A path with no repeated edges

Circuit/Cycle A path that starts and ends at the same vertex

Simple circuit A circuit with no repeated edges except the start=end vertex

8.2 Connected vs Disconnected Graphs

A graph is connected if there is a path between every pair of vertices. A connected component is a maximal
connected subgraph. For directed graphs, we distinguish strongly connected (path from every vertex to every
other in both directions) vs weakly connected (connected if directions ignored).

8.3 Cut Vertices and Bridges

CRITICAL CONCEPT

A CUT VERTEX (articulation point) is a vertex whose removal disconnects the graph. A BRIDGE is an edge
whose removal disconnects the graph. These identify single points of failure in networks.

■ Connection to Real Networks: Internet routers identified as cut vertices are critical infrastructure. Network engineers
specifically design redundant paths to eliminate bridges and cut vertices.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 12

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 9 Euler & Hamilton Paths

Two famous traversal problems with very different solutions

9.1 The Königsberg Bridge Problem

Euler solved the famous Königsberg bridge problem in 1736 — can you walk across all 7 bridges exactly once? He
proved it was IMPOSSIBLE, founding graph theory in the process. The city's 4 landmasses are vertices; each bridge
is an edge. The problem asks for an Euler path.

9.2 Euler Paths and Circuits

What Condition Note

Euler Circuit Every vertex has EVEN degree Start and end at same vertex

Euler Path Exactly TWO vertices have ODD Start and end at those 2 vertices
degree

Neither More than 2 vertices with odd No Eulerian traversal possible

degree

9.3 Hamilton Paths and Cycles

KEY DIFFERENCE

Euler paths visit every EDGE exactly once. Hamilton paths visit every VERTEX exactly once. Despite the
similarity, no simple condition like Euler's degree rule exists for Hamiltonicity — it is an NP-complete problem in
general.

Theorem Condition Guarantees

Dirac's Every vertex has degree ≥ n/2 (n = Hamilton cycle exists

#vertices)

Ore's For every non-adjacent pair u,v: Hamilton cycle exists

deg(u)+deg(v) ≥ n

■ The Travelling Salesman Problem (TSP) — find the shortest Hamiltonian cycle in a weighted graph — is one of
the most important NP-hard problems in computer science!

■ Connection: Euler circuits are used in route planning (garbage trucks, mail delivery). Hamilton cycles model the TSP,
DNA sequencing, and circuit board drilling optimization.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 13

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 10 Shortest-Path Problems

Finding the fastest route through weighted graphs

10.1 Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with
non-negative edge weights. It uses a greedy approach — always selecting the unvisited vertex with the minimum
known distance.

Steps:
Step 1: Initialize: dist[source] = 0; dist[all others] = ∞; mark all unvisited
Step 2: Select the unvisited vertex u with minimum dist[u]
Step 3: For each unvisited neighbor v of u: if dist[u] + weight(u,v) < dist[v], update dist[v]
Step 4: Mark u as visited
Step 5: Repeat steps 2-4 until all vertices are visited
Step 6: Result: dist[] contains shortest distances from source to every vertex

Time Complexity: O((V + E) log V) with a min-heap / priority queue

■ Dijkstra's algorithm FAILS with negative edge weights. Use Bellman-Ford (O(VE)) when negative weights
are present.

10.2 Comparison of Shortest Path Algorithms

Algorithm Complexity Negative Weights? Best Used For

Dijkstra O((V+E)logV) No Single-source,

non-negative weights

Bellman-Ford O(VE) Yes Negative weights, detects

negative cycles

Floyd-Warshall O(V³) Yes All-pairs shortest paths

BFS O(V+E) N/A (unweighted) Unweighted graphs

■ Connection: Dijkstra's algorithm powers GPS navigation, network routing protocols (OSPF), and social network
'degrees of separation' calculations.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 14

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 11 Graph Coloring

Assigning colours so no two adjacent vertices share the same colour

11.1 Chromatic Number

KEY DEFINITION

The CHROMATIC NUMBER χ(G) is the minimum number of colours needed to colour the vertices of G such that
no two adjacent vertices have the same colour.

Graph Type Chromatic Number Reason

Empty graph (no edges) 1 All vertices same colour

Bipartite graph 2 Two-colour alternately

Odd cycle C2k+1 3 Can't 2-colour odd cycles

Even cycle C2k 2 Alternating 2-colour works

Complete graph Kn n Every pair adjacent

Tree 2 Trees are bipartite

Planar graph ≤4 Four Color Theorem

■ THE FOUR COLOR THEOREM (1976): Any planar map can be coloured with at most 4 colours so that no two
adjacent regions share a colour. This was the first major theorem proved with computer assistance.

11.2 Applications
• Scheduling problems: Tasks = vertices; conflicts = edges; colours = time slots
• Register allocation in compilers: Variables = vertices; concurrent use = edges
• Frequency assignment: Transmitters = vertices; interference = edges; frequencies = colours
• Sudoku puzzles: Cells = vertices; same row/col/box = edges; digits = colours
• Exam timetabling: Subjects = vertices; shared students = edges; slots = colours

■ Connection: Graph coloring is NP-complete in general (finding χ(G) for arbitrary graphs). But polynomial-time
algorithms exist for special graph classes like bipartite and planar graphs.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 15

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 12 Trees
Connected acyclic graphs — the backbone of computer science data
structures

12.1 Properties of Trees

EQUIVALENT DEFINITIONS OF A TREE

A connected graph with no cycles. These all say the same thing: (1) Connected + acyclic, (2) Connected with V−1
edges, (3) Acyclic with V−1 edges, (4) Unique path between every pair of vertices.

A tree with n vertices has exactly n − 1 edges.

12.2 Rooted Trees

• Root: the designated top vertex
• Parent: the vertex directly above another in the tree
• Child: a vertex directly below a parent
• Leaf (external node): a vertex with no children
• Internal node: a vertex with at least one child
• Height: length of the longest path from root to a leaf
• Level: distance from root (root is level 0)
• Depth: level of a vertex
• Subtree: a vertex and all its descendants

12.3 Binary Trees

A binary tree is a rooted tree where each node has at most 2 children (left child and right child). A full binary tree
has every internal node with exactly 2 children. A complete binary tree fills all levels left to right.

Full binary tree with i internal nodes → i+1 leaf nodes

Complete binary tree with n nodes → height = ■log2 n■

■ Binary search trees enable O(log n) search, insert, and delete — far better than O(n) linear search. This is WHY
balanced trees (AVL, Red-Black) are critical in databases.

■ Connection: Virtually every CS data structure uses trees: file systems, XML/HTML DOM, decision trees in ML, syntax
trees in compilers, heaps in priority queues.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 16

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 13 Spanning Trees

Connecting all vertices with minimum structure

13.1 What is a Spanning Tree?

A spanning tree of a connected graph G is a subgraph that is a tree AND includes every vertex of G. A graph can
have many spanning trees. A minimum spanning tree (MST) of a weighted graph has the minimum total edge
weight.

13.2 Prim's Algorithm (Greedy — Grow a tree)

1. Start with any vertex; mark it visited
2. Repeatedly add the minimum-weight edge that connects a visited vertex to an unvisited one
3. Stop when all vertices are included
4. Time complexity: O(E log V) with a priority queue

13.3 Kruskal's Algorithm (Greedy — Add edges by weight)

1. Sort ALL edges by weight (ascending)
2. Add the next lightest edge to the MST, provided it does NOT create a cycle
3. Use Union-Find (Disjoint Set Union) to detect cycles efficiently
4. Stop when MST has V−1 edges
5. Time complexity: O(E log E) dominated by sorting

■ Both Prim's and Kruskal's always produce a correct MST, but Prim's is better for dense graphs (many edges)
while Kruskal's is better for sparse graphs.

13.4 Backtracking
Backtracking is a systematic method for exploring all possible solutions by building candidates incrementally and
abandoning (backtracking) a candidate as soon as it is determined it cannot lead to a valid solution.

■ Connection: Spanning trees are used in network broadcast (minimum redundancy), circuit design, cluster analysis, and
approximation algorithms for TSP.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 17

EMTH403 · Mathematical Foundation for Computer Science Study Guide

UNIT 14 Tree Traversal

Visiting every node systematically — the foundation of tree algorithms

14.1 The Three DFS Traversals

Traversal Order Visit Node Use Case

Preorder Root → Left → Right BEFORE children Copy tree, serialize tree,
prefix expressions

Inorder Left → Root → Right BETWEEN children BST → sorted sequence

(ascending order)

Postorder Left → Right → Root AFTER children Delete tree, evaluate

postfix, dependency
resolution

■ INORDER traversal of a Binary Search Tree always produces the nodes in SORTED ASCENDING ORDER. This
is the key property linking BSTs to sorting.

14.2 Expression Trees

An expression tree represents a mathematical expression as a binary tree where leaf nodes are operands
(numbers/variables) and internal nodes are operators (+, -, *, /).

• Preorder traversal → Prefix notation (Polish notation): + * 2 3 4

• Inorder traversal → Infix notation (standard): 2 * 3 + 4
• Postorder traversal → Postfix notation (Reverse Polish): 2 3 * 4 +
Expression (2 × 3) + 4 → Prefix: + × 2 3 4 | Postfix: 2 3 × 4 +

14.3 BFS vs DFS — The Big Picture

Property BFS (Breadth-First) DFS (Depth-First)

Data Structure Queue Stack (or recursion)

Visits Level by level Goes as deep as possible first

Shortest Path Finds shortest path (unweighted) Does NOT guarantee shortest path

Memory O(V) — stores entire level O(h) — h = tree height

Best for Nearby nodes, level-order tasks Topological sort, cycle detection

Spanning Tree BFS spanning tree DFS spanning tree (back/forward

edges)

■ Connection: Postfix evaluation is used by stack-based virtual machines (JVM, Python's CPython). Compilers parse
expressions into syntax trees and traverse them for code generation.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 18

EMTH403 · Mathematical Foundation for Computer Science Study Guide

BONUS Hidden Connections Across the Course

How all 14 units connect — patterns you might have missed

The Big Picture: Logic → Structure → Graphs → Algorithms

Logic (Units 1-2) Boolean Algebra (Unit 4)
■
Boolean algebra IS propositional logic — AND/OR/NOT are ∧/∨/¬. Logic gates implement propositions in
hardware.

Posets (Unit 3) Trees (Unit 12)

■
Every tree defines a partial order (ancestor relationship). Every finite lattice can be drawn as a Hasse
diagram that looks like a tree.

Boolean Algebra (Unit 4) Graph Coloring (Unit 11)

■
Simplifying a Boolean function is equivalent to minimising the chromatic number of an implication graph.

Counting (Unit 5) Graph Theory (Units 6-14)

■
Counting paths, spanning trees (Cayley's formula: n^(n-2) spanning trees for Kn), and colorings all require
combinatorics.

Euler Paths (Unit 9) Connectivity (Unit 8)

■
Euler's theorem requires ALL vertices to have even degree — which is a connectivity/degree property.

Shortest Paths (Unit 10) Spanning Trees (Unit 13)

■
Dijkstra's algorithm builds a SHORTEST PATH TREE, which is itself a spanning tree of the graph.

Trees (Unit 12) Traversal (Unit 14)

■
Traversal ORDER defines the tree's structure. Inorder uniquely reconstructs a BST; pre+inorder uniquely
reconstructs any binary tree.

Hamilton Paths (Unit 9) Graph Coloring (Unit 11)

■
Both are NP-complete problems — connected to the deep question of P vs NP in complexity theory.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 19

EMTH403 · Mathematical Foundation for Computer Science Study Guide

QUICK REF
ERENCE Exam Cheat Sheet
The most important facts, formulas, and theorems

Must-Know Formulas
Handshaking Σ deg(v) = 2|E|

Euler circuit All degrees even

Euler path Exactly 2 odd-degree vertices

Dirac's theorem deg(v) ≥ n/2 for all v → Hamilton cycle

Tree edges |E| = |V| − 1

Full binary tree i internal nodes → i+1 leaves

Planar graph E ≤ 3V − 6

Euler's formula V − E + F = 2

Permutation P(n,r) = n!/(n−r)!

Combination C(n,r) = n!/[r!(n−r)!]

Inclusion-Exclusion |A∪B| = |A|+|B|−|A∩B|

Chromatic (planar) χ(G) ≤ 4 (Four Color Theorem)

Complete graph Kn χ(Kn) = n, edges = n(n−1)/2

Cayley's formula Kn has n^(n-2) spanning trees

Complete binary tree Height = ■log■ n■

■ FINAL INSIGHT: This entire course is about one idea — STRUCTURE. Logic structures truth. Algebra structures
operations. Posets/Lattices structure comparisons. Graphs structure relationships. Trees structure hierarchies.
Algorithms navigate these structures efficiently.

Dr. Kulwinder Singh (Ed.) · Lovely Professional University Page 20