Discrete Mathematics & Graph Theory exam preparation.
Practice questions for every unit in the style of the R23 end exam, a model answer for each, and a one-page revision summary. Built on the official syllabus units.
- Practice questions in the exam's style
- Drafted with AI and checked by a second AI pass. Doubtful points were verified against public sources. Report a mistake
- Units
- 5
- Questions
- 60
- 2-mark
- 30
- 10-mark
- 30
- Done
- Checked on
Exam guide
Paper pattern
Semester-end theory paper, 70 marks, from the JNTUK B.Tech R23 Regulations, end-examination pattern for theory subjects.
- Question 1 · 20 marksTen compulsory short-answer questions of 2 marks each (two from every unit).
- Questions 2 to 6 · 50 marksFive either/or questions of 10 marks each, one per unit. You answer one of the two in each.
- The semester-end examination carries 70 marks; internal assessment carries 30.
- Mid-semester examinations are separate: a 20-minute objective paper (10 marks) and a 90-minute subjective paper with three either/or questions of 10 marks (condensed to 15 marks).
- The regulations text does not state the length of the end examination. Use the duration printed on your hall ticket or question paper.
How to split your time
This plan assumes a 3-hour paper. If yours is different, keep the same proportions. Marks per minute stay roughly even across Question 1 and the 10-mark answers.
- 10 minRead the paper and choose one option in each either/or question
- 30 minQuestion 1: ten short answers (about 3 minutes each)
- 130 minQuestions 2 to 6: one 10-mark answer per unit (about 26 minutes each)
- 10 minFinal check of numbering, calculations and diagrams
Study tips for Discrete Mathematics & Graph Theory
- Practise logic by hand. Build truth tables carefully, prove equivalences one line at a time, and name the law used at each line (De Morgan, distributive, absorption and so on). In inference problems, label every line with its rule (rule P, rule T, conditional proof), so an examiner can follow your derivation.
- For counting problems, first decide whether order matters and whether repetition is allowed. Write the general formula, such as n!/(r!(n-r)!), before you substitute values. Check small cases by listing the outcomes to confirm your method. For recurrence relations, write the characteristic equation clearly, then check your closed form against the first few terms given by the recurrence.
- For properties of relations and functions (reflexive, symmetric, transitive, antisymmetric, injective, surjective), test each property separately. One counterexample is enough to show a property fails. To show a property holds, you need an argument that covers all elements, or a complete check of every pair when the set is finite. Never treat a single example as a proof.
- Draw graphs and Hasse diagrams neatly, with every vertex and edge labelled. Practise running Prim's and Kruskal's algorithms and building BFS and DFS spanning trees in a step-by-step table, so that each edge choice or vertex visit is visible. Check that a spanning tree on n vertices has exactly n-1 edges and no cycle.
- In every proof, state what is given and what must be shown, and name your method (direct proof, indirect proof by contradiction or contrapositive). Mathematical induction is still a useful tool, for example to verify the solution of a recurrence. Finish with a clear concluding statement, and check numerical answers by substituting them back.
Mathematical Logic
Syllabus: Statements and notations; Connectives; Well formed formulas; Truth tables; Tautologies; Equivalence of formulas; Duality law; Tautological implications; Normal forms; Theory of inference for statement calculus; Consistency of premises; Indirect method of proof; Predicates and predicative logic; Statement functions, variables and quantifiers; Free and bound variables; Inference theory for predicate calculus
One-page revision summary
- A statement is a declarative sentence that is either true or false but not both, and is denoted by letters such as P, Q and R.
- The connectives are ¬, ∧, ∨, → and ↔; the conditional P → Q is false only when P is true and Q is false.
- A well-formed formula is built recursively from statement variables using connectives and proper parentheses.
- A truth table for a formula in n variables has 2^n rows.
- A tautology is always true, a contradiction is always false, and a contingency is neither.
- A ⇔ B exactly when A ↔ B is a tautology, and equivalences can be proved with standard laws instead of truth tables.
- The dual of a formula built from ¬, ∧ and ∨ swaps ∧ with ∨ and T with F, and duals of equivalent formulas are equivalent.
- A ⇒ B exactly when A → B is a tautology; modus ponens, modus tollens, disjunctive syllogism and hypothetical syllogism are the key implications.
- The PDNF is the disjunction of the minterms of the true rows, the PCNF is the conjunction of the maxterms of the false rows, and both are unique.
- Rule P introduces premises, Rule T introduces implied formulas, and Rule CP derives S → R by assuming S.
- Premises are consistent if some assignment makes all of them true, and inconsistent premises imply every conclusion.
- The indirect method adds the negation of the conclusion as a premise and derives a contradiction R ∧ ¬R.
- A predicate expresses a property or relation, and an n-place predicate takes n arguments.
- A statement function such as P(x) becomes a statement only after substitution or quantification; ∀ usually pairs with → and ∃ with ∧.
- A variable occurrence inside the scope of a quantifier on it is bound, otherwise it is free, and a formula with free variables is not a statement.
- The predicate rules are US, ES, EG and UG; ES must introduce a new constant and UG must not be applied to a constant obtained by ES.
- The order of mixed quantifiers matters: ∀x∃y A(x, y) does not imply ∃y∀x A(x, y).
Learn these by heart
- P → Q ⇔ ¬P ∨ Q and P ↔ Q ⇔ (P → Q) ∧ (Q → P)
- De Morgan: ¬(P ∧ Q) ⇔ ¬P ∨ ¬Q and ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q
- Quantifier negation: ¬∀x A(x) ⇔ ∃x ¬A(x) and ¬∃x A(x) ⇔ ∀x ¬A(x)
- A ⇒ B iff A → B is a tautology; A ⇔ B iff A ↔ B is a tautology
- Modus ponens: P, P → Q ⇒ Q; modus tollens: ¬Q, P → Q ⇒ ¬P; disjunctive syllogism: ¬P, P ∨ Q ⇒ Q; hypothetical syllogism: P → Q, Q → R ⇒ P → R
- PDNF uses the minterms of the true rows and PCNF uses the maxterms of the false rows; (number of minterms) + (number of maxterms) = 2^n
- Apply ES before US, use a new constant for ES, and apply UG only to an arbitrary variable
2-mark questions
1 What is a statement (proposition)? Distinguish atomic and compound statements and state the notation used. 2 marks
A statement is a declarative sentence that is either true or false, but not both. For example, '7 is a prime number' is true. Statements are denoted by capital letters such as P, Q and R. An atomic statement cannot be split further. A compound statement joins atomic statements with connectives, for example P ∧ Q.
2 Define a well-formed formula (wff) of statement calculus. 2 marks
A wff is defined recursively. (1) Every statement variable and the constants T and F are wffs. (2) If A is a wff, then ¬A is a wff. (3) If A and B are wffs, then (A ∧ B), (A ∨ B), (A → B) and (A ↔ B) are wffs. (4) Nothing else is a wff. For example, (P → (Q ∨ ¬R)) is a wff, but P ∧ → Q is not.
3 State the duality law and write the dual of ¬(P ∨ Q) ∧ (P ∨ F). 2 marks
The dual A* of a formula that uses only ¬, ∧ and ∨ is obtained by interchanging ∧ with ∨ and T with F. The duality law states that if A ⇔ B, then A* ⇔ B*.
The dual of ¬(P ∨ Q) ∧ (P ∨ F) is ¬(P ∧ Q) ∨ (P ∧ T).
4 Define tautological implication and show that P ∧ Q ⇒ P. 2 marks
A tautologically implies B, written A ⇒ B, when A → B is a tautology. In other words, B is true whenever A is true.
We have (P ∧ Q) → P ⇔ ¬(P ∧ Q) ∨ P ⇔ ¬P ∨ ¬Q ∨ P ⇔ T ∨ ¬Q ⇔ T.
The conditional is a tautology, so P ∧ Q ⇒ P.
5 When is a set of premises said to be inconsistent? Test the set {P → Q, P, ¬Q}. 2 marks
Premises H1, H2, ..., Hn are consistent if at least one truth assignment makes all of them true. They are inconsistent if H1 ∧ H2 ∧ ... ∧ Hn is a contradiction.
In the given set, P and P → Q force Q to be true, which contradicts ¬Q. Hence the set is inconsistent.
6 Identify the free and bound occurrences of variables in ∀x(P(x) → Q(x, y)) ∧ R(x). 2 marks
The scope of ∀x is (P(x) → Q(x, y)).
- The occurrences of x in P(x) and Q(x, y) lie inside this scope, so they are bound.
- y is not quantified anywhere, so it is free.
- The x in R(x) lies outside the scope of ∀x, so that occurrence is free.
10-mark questions
1 Explain the five basic logical connectives with their truth tables. Construct the truth table of ((P → Q) ∧ (Q → R)) → (P → R) and decide whether it is a tautology, a contradiction or a contingency. 10 marks
Connectives combine simple statements into compound statements. The truth value of a compound statement depends only on the truth values of its parts and the connective used.
Step 1: The five connectives
- Negation ¬P (not P) is true exactly when P is false.
- Conjunction P ∧ Q (P and Q) is true only when both P and Q are true.
- Disjunction P ∨ Q (P or Q) is false only when both are false.
- Conditional P → Q (if P then Q) is false only when P is true and Q is false.
- Biconditional P ↔ Q (P if and only if Q) is true when P and Q have the same truth value.
P Q | ¬P | P∧Q | P∨Q | P→Q | P↔Q
T T | F | T | T | T | T
T F | F | F | T | F | F
F T | T | F | T | T | F
F F | T | F | F | T | TStep 2: Set up the table for the given formula There are 3 variables, so the table has 2^3 = 8 rows. Let A = (P → Q) ∧ (Q → R) and B = P → R. The formula is A → B.
Step 3: Fill the columns
P Q R | P→Q | Q→R | A | P→R | A→B
T T T | T | T | T | T | T
T T F | T | F | F | F | T
T F T | F | T | F | T | T
T F F | F | T | F | F | T
F T T | T | T | T | T | T
F T F | T | F | F | T | T
F F T | T | T | T | T | T
F F F | T | T | T | T | TStep 4: Check the critical rows A → B can be false only when A is true and B is false. B = P → R is false only in rows TTF and TFF. In both of these rows A is false:
- In row TTF, Q → R is false.
- In row TFF, P → Q is false.
So the case 'A true and B false' never occurs.
Step 5: Classify A formula is a tautology if its last column is all T, a contradiction if it is all F, and a contingency otherwise. Here every entry of the last column is T.
Conclusion: ((P → Q) ∧ (Q → R)) → (P → R) is a tautology. Therefore (P → Q) ∧ (Q → R) ⇒ (P → R). This is the hypothetical syllogism rule used in inference.
2 Without using truth tables, prove (a) (P → Q) ∧ (P → R) ⇔ P → (Q ∧ R) and (b) that (P ∧ Q) → (P ∨ Q) is a tautology. Also explain the duality law using the result of (a). 10 marks
Two formulas A and B are equivalent, written A ⇔ B, if they have the same truth value under every assignment. Equivalently, A ↔ B is a tautology. Instead of building truth tables, we can transform one formula into the other using standard laws.
Step 1: Laws used
- Implication: P → Q ⇔ ¬P ∨ Q
- Double negation: ¬¬P ⇔ P
- Commutative and associative laws for ∧ and ∨
- Distributive: P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R) and P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)
- De Morgan: ¬(P ∧ Q) ⇔ ¬P ∨ ¬Q and ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q
- Complement: P ∨ ¬P ⇔ T and P ∧ ¬P ⇔ F
- Domination: P ∨ T ⇔ T
Step 2: Proof of (a) (P → Q) ∧ (P → R) ⇔ (¬P ∨ Q) ∧ (¬P ∨ R) (implication law) ⇔ ¬P ∨ (Q ∧ R) (distributive law, read from right to left) ⇔ P → (Q ∧ R) (implication law) Hence (a) is proved.
Step 3: Proof of (b) (P ∧ Q) → (P ∨ Q) ⇔ ¬(P ∧ Q) ∨ (P ∨ Q) (implication law) ⇔ (¬P ∨ ¬Q) ∨ (P ∨ Q) (De Morgan) ⇔ (¬P ∨ P) ∨ (¬Q ∨ Q) (commutative and associative laws) ⇔ T ∨ T (complement law) ⇔ T (domination law) The formula is a tautology, which also shows that P ∧ Q ⇒ P ∨ Q.
Step 4: Duality law The dual A* of a formula built only from ¬, ∧ and ∨ is obtained by interchanging ∧ with ∨ and T with F. The duality law states that if A ⇔ B, then A* ⇔ B*.
First rewrite (a) using only ¬, ∧ and ∨: (¬P ∨ Q) ∧ (¬P ∨ R) ⇔ ¬P ∨ (Q ∧ R)
Its dual is: (¬P ∧ Q) ∨ (¬P ∧ R) ⇔ ¬P ∧ (Q ∨ R)
This is the other distributive law, so it is valid, exactly as the duality law predicts. In the same way, the dual of P ∨ ¬P ⇔ T is P ∧ ¬P ⇔ F.
Conclusion: Equivalence laws give short and rigorous proofs without 2^n-row tables. The duality law then supplies a second valid equivalence free of cost from every one we prove.
3 Define minterms, maxterms, PDNF and PCNF. Obtain the principal disjunctive normal form and the principal conjunctive normal form of (P ∧ Q) ∨ (¬P ∧ R). 10 marks
A normal form writes a formula in a standard shape.
- A disjunctive normal form (DNF) is a disjunction of elementary products.
- A conjunctive normal form (CNF) is a conjunction of elementary sums.
These forms are not unique, so principal forms are used.
Step 1: Definitions
- A minterm in n variables is a conjunction in which each variable appears exactly once, either plain or negated. There are 2^n minterms.
- A maxterm is a disjunction in which each variable appears exactly once, either plain or negated.
- The PDNF is the disjunction of the minterms for the rows where the formula is true.
- The PCNF is the conjunction of the maxterms for the rows where the formula is false.
- Both forms are unique for a given formula.
Step 2: Truth table of F = (P ∧ Q) ∨ (¬P ∧ R)
P Q R | P∧Q | ¬P∧R | F
T T T | T | F | T
T T F | T | F | T
T F T | F | F | F
T F F | F | F | F
F T T | F | T | T
F T F | F | F | F
F F T | F | T | T
F F F | F | F | FStep 3: PDNF from the true rows In a minterm, a variable that is T in the row appears plain and a variable that is F appears negated.
- TTT gives P ∧ Q ∧ R
- TTF gives P ∧ Q ∧ ¬R
- FTT gives ¬P ∧ Q ∧ R
- FFT gives ¬P ∧ ¬Q ∧ R
PDNF = (P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R) ∨ (¬P ∧ Q ∧ R) ∨ (¬P ∧ ¬Q ∧ R)
Step 4: Algebraic check Each term is expanded with the missing variable:
- P ∧ Q ⇔ (P ∧ Q) ∧ (R ∨ ¬R) ⇔ (P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ¬R)
- ¬P ∧ R ⇔ (¬P ∧ R) ∧ (Q ∨ ¬Q) ⇔ (¬P ∧ Q ∧ R) ∨ (¬P ∧ ¬Q ∧ R)
The same four minterms appear, which confirms the PDNF.
Step 5: PCNF from the false rows In a maxterm, a variable that is T in the row appears negated and a variable that is F appears plain.
- TFT gives ¬P ∨ Q ∨ ¬R
- TFF gives ¬P ∨ Q ∨ R
- FTF gives P ∨ ¬Q ∨ R
- FFF gives P ∨ Q ∨ R
PCNF = (¬P ∨ Q ∨ ¬R) ∧ (¬P ∨ Q ∨ R) ∧ (P ∨ ¬Q ∨ R) ∧ (P ∨ Q ∨ R)
Step 6: Consistency check There are 4 minterms and 4 maxterms, and 4 + 4 = 8 = 2^3. Every row is accounted for exactly once.
Conclusion: The PDNF has four minterms and the PCNF has four maxterms. Either form can be used to test whether two formulas are equivalent, because equivalent formulas have identical principal normal forms.
4 Explain the rules P, T and CP of the theory of inference for statement calculus and list the main tautological implications. Using the indirect method of proof, show that ¬A follows from the premises A → B, B → C, ¬C ∨ D and ¬D. 10 marks
In statement calculus, a conclusion C follows validly from premises H1, H2, ..., Hn when H1 ∧ H2 ∧ ... ∧ Hn ⇒ C. A derivation is a numbered list of formulas, and each line is justified by a rule.
Step 1: Rules of inference
- Rule P: a premise may be introduced at any step.
- Rule T: a formula S may be introduced if S is tautologically implied by one or more earlier formulas.
- Rule CP (conditional proof): if R can be derived from the premises together with S, then S → R can be derived from the premises alone.
Step 2: Main tautological implications
- Modus ponens: P, P → Q ⇒ Q
- Modus tollens: ¬Q, P → Q ⇒ ¬P
- Disjunctive syllogism: ¬P, P ∨ Q ⇒ Q
- Hypothetical syllogism: P → Q, Q → R ⇒ P → R
- Simplification: P ∧ Q ⇒ P
- Addition: P ⇒ P ∨ Q
- Conjunction: P, Q ⇒ P ∧ Q
Step 3: Indirect method To prove C, add ¬C as an extra premise and derive a contradiction of the form R ∧ ¬R. The premises together with ¬C are then inconsistent. So ¬C cannot be true when the premises are true, and C follows.
Step 4: Derivation The conclusion is ¬A, so its negation ¬¬A ⇔ A is added as an assumed premise.
1. {1} A → B Rule P
2. {2} B → C Rule P
3. {3} ¬C ∨ D Rule P
4. {4} ¬D Rule P
5. {5} A Rule P (assumed, negation of conclusion)
6. {1,5} B Rule T, 1, 5, modus ponens
7. {1,2,5} C Rule T, 2, 6, modus ponens
8. {3,4} ¬C Rule T, 3, 4, disjunctive syllogism
9. {1,2,3,4,5} C ∧ ¬C Rule T, 7, 8, conjunctionStep 5: Interpretation Line 9 is a contradiction. So the original premises together with A are inconsistent. Hence A must be false whenever all the premises are true, which means ¬A follows.
Step 6: Cross-check by a direct proof
- From ¬C ∨ D and ¬D we get ¬C (disjunctive syllogism).
- From B → C and ¬C we get ¬B (modus tollens).
- From A → B and ¬B we get ¬A (modus tollens).
The same conclusion is reached.
Conclusion: The rules P, T and CP, together with the standard implications, give mechanical and checkable proofs. The indirect method is especially convenient when the conclusion is a negation.
5 Explain predicates, statement functions, quantifiers, and free and bound variables with examples. Symbolise statements using quantifiers and show that the order of quantifiers matters. 10 marks
Statement calculus treats a simple statement as a whole. It cannot express the common structure of sentences such as 'Ravi is a student' and 'Sita is a student'. Predicate logic removes this limitation by separating the subject from the property.
Step 1: Predicates A predicate is the part of a statement that describes a property of an object or a relation among objects.
- In 'Ravi is a student', the predicate 'is a student' is written S, and the statement becomes S(r).
- A relation such as 'x is greater than y' is a 2-place predicate G(x, y).
Step 2: Statement functions and variables A simple statement function is an expression such as P(x), where P is a predicate and x is an individual variable.
- P(x) is not a statement, because it has no truth value until x is replaced by an object or is quantified.
- For example, if P(x) means 'x is prime', then P(5) is true and P(8) is false.
- The set of objects that x may stand for is the universe of discourse.
Step 3: Quantifiers
- The universal quantifier ∀x A(x) means 'for every x in the universe, A(x)'.
- The existential quantifier ∃x A(x) means 'there is at least one x such that A(x)'.
- Negation rules: ¬∀x A(x) ⇔ ∃x ¬A(x) and ¬∃x A(x) ⇔ ∀x ¬A(x).
Step 4: Symbolisation examples
- 'Every CSE student studies logic': ∀x(C(x) → L(x)).
- 'Some prime numbers are even': ∃x(P(x) ∧ E(x)).
- 'Not every student owns a laptop': ¬∀x(S(x) → O(x)), which is equivalent to ∃x(S(x) ∧ ¬O(x)).
Note that ∀ normally goes with → and ∃ goes with ∧. Writing ∃x(P(x) → E(x)) would be wrong, because it is true even if nothing is prime.
Step 5: Free and bound variables The scope of a quantifier is the formula immediately following it. An occurrence of a variable inside the scope of a quantifier on that variable is bound; otherwise it is free.
Consider ∃y G(x, y) ∧ P(y):
- y in G(x, y) is bound.
- x is free.
- y in P(y) is free, because it lies outside the scope.
A formula with free variables is not yet a statement.
Step 6: Order of quantifiers Take the integers as the universe and let G(y, x) mean y > x.
- ∀x ∃y G(y, x) says that every integer has a larger integer. This is true, by taking y = x + 1.
- ∃y ∀x G(y, x) says that some integer is larger than every integer. This is false, since such a y would have to be larger than itself.
Conclusion: Predicates, quantifiers and the careful tracking of free and bound variables let us express mathematical and everyday reasoning precisely. The order of mixed quantifiers can change the meaning completely.
6 State the rules US, ES, EG and UG of inference theory for predicate calculus with their restrictions. Using them, prove (a) ∀x(P(x) → Q(x)), ∀x(Q(x) → R(x)) ⇒ ∀x(P(x) → R(x)) and (b) 'Every programmer knows logic. Some students are programmers. Therefore some students know logic.' 10 marks
Inference in predicate calculus uses all the rules of statement calculus (P, T, CP). It adds four rules that remove quantifiers so that statement rules can be applied, and then put quantifiers back.
Step 1: The four rules
- Universal Specification (US): from ∀x A(x), infer A(y) for any object y.
- Existential Specification (ES): from ∃x A(x), infer A(c), where c is a new constant that has not appeared earlier in the derivation.
- Existential Generalisation (EG): from A(c), infer ∃x A(x).
- Universal Generalisation (UG): from A(y), infer ∀x A(x), provided y is arbitrary. This means y must not have been introduced by ES and must not occur free in any premise.
A practical guideline: when both kinds of premise are present, apply ES before US. US may be applied to any object, including the constant already introduced by ES, but ES must always introduce a new constant.
Step 2: Proof of (a)
1. ∀x(P(x) → Q(x)) Rule P
2. P(y) → Q(y) US, 1
3. ∀x(Q(x) → R(x)) Rule P
4. Q(y) → R(y) US, 3
5. P(y) → R(y) Rule T, 2, 4, hypothetical syllogism
6. ∀x(P(x) → R(x)) UG, 5UG is valid in line 6 because y was obtained only by US, so it is arbitrary.
Step 3: Symbolising (b) Let S(x) mean 'x is a student', G(x) mean 'x is a programmer' and L(x) mean 'x knows logic'.
- Premises: ∀x(G(x) → L(x)) and ∃x(S(x) ∧ G(x)).
- Conclusion: ∃x(S(x) ∧ L(x)).
Step 4: Proof of (b)
1. ∃x(S(x) ∧ G(x)) Rule P
2. S(a) ∧ G(a) ES, 1 (a is new)
3. ∀x(G(x) → L(x)) Rule P
4. G(a) → L(a) US, 3
5. G(a) Rule T, 2, simplification
6. L(a) Rule T, 4, 5, modus ponens
7. S(a) Rule T, 2, simplification
8. S(a) ∧ L(a) Rule T, 6, 7, conjunction
9. ∃x(S(x) ∧ L(x)) EG, 8Step 5: Why the order matters If US had been applied first to produce G(a) → L(a), then ES could not reuse the constant a, because a would no longer be new. The derivation would break down. Applying ES first avoids this. Also, UG cannot be applied to S(a) ∧ L(a), because a came from ES. This is why the conclusion is existential and not universal.
Conclusion: US and ES strip off quantifiers, statement rules do the reasoning, and EG or UG restore the required quantifier. Both arguments are therefore valid.
Set Theory
Syllabus: Sets and operations on sets; Principle of inclusion-exclusion; Relations: properties and operations; Partition and covering; Transitive closure; Equivalence, compatibility and partial ordering; Hasse diagrams; Functions: bijective, composition and inverse; Permutation functions and recursive functions; Lattices and their properties
One-page revision summary
- Sets are combined by union, intersection, difference, complement and symmetric difference, and these operations obey the commutative, associative, distributive and De Morgan laws.
- An n-element set has 2^n subsets in its power set, and the Cartesian product A × B has |A|·|B| ordered pairs.
- Inclusion–exclusion corrects overcounting by alternately subtracting and adding the sizes of intersections, and is often combined with the complement to count elements in none of the sets.
- A relation on A is a subset of A × A, so an n-element set has 2^(n²) relations, which can be represented by 0–1 matrices or digraphs.
- Operations on relations include union, intersection, complement, inverse and composition, and the matrix of 'first R then S' is the Boolean product of M_R and M_S.
- Worked example: on {1, 2, 3, 4}, if R = {(1, 2), (2, 3)} and S = {(2, 4), (3, 1)}, then 'first R then S' is S∘R = {(1, 4), (2, 1)}, which are exactly the 1-entries of the Boolean product of M_R and M_S.
- A partition has non-empty, pairwise disjoint blocks whose union is the set, while a covering only requires the union to be the set and allows overlaps.
- The transitive closure is R⁺ = R ∪ R² ∪ … ∪ Rⁿ, and Warshall's algorithm finds it in O(n³) steps.
- Equivalence relations and partitions correspond one-to-one: the equivalence classes form the blocks, and the blocks define the relation.
- A compatibility relation (reflexive and symmetric) gives maximal compatibility blocks that form a covering, not necessarily a partition.
- A partial order is reflexive, antisymmetric and transitive, and a total order additionally makes every pair of elements comparable.
- A Hasse diagram shows only covering relations, with smaller elements lower and with no loops, transitive edges or arrowheads.
- In a poset, greatest and least elements are unique when they exist, while there may be several maximal or minimal elements.
- A function is bijective if it is both one-one and onto, and only bijections have inverse functions.
- Composition of functions is associative but generally not commutative.
- A permutation is a bijection of a finite set onto itself; an n-element set has n! permutations, which can be written in two-line or cycle notation.
- Primitive recursive functions are built from the zero, successor and projection functions using composition and primitive recursion; addition, multiplication and factorial are examples.
- A lattice is bounded if it has a least and a greatest element, complemented if every element has a complement, and a Boolean algebra if it is both complemented and distributive.
Learn these by heart
- |A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|
- Equivalence relation = reflexive + symmetric + transitive; partial order = reflexive + antisymmetric + transitive; compatibility relation = reflexive + symmetric.
- Warshall's rule: W_k[i][j] = W_(k−1)[i][j] ∨ (W_(k−1)[i][k] ∧ W_(k−1)[k][j]).
- For bijections f and g: (g∘f)⁻¹ = f⁻¹∘g⁻¹.
- In any lattice: a ≤ b ⇔ a ∧ b = a ⇔ a ∨ b = b, and the absorption laws a ∨ (a ∧ b) = a and a ∧ (a ∨ b) = a hold.
- In the divisor lattice D_n: a ∧ b = gcd(a, b) and a ∨ b = lcm(a, b).
2-mark questions
1 Let A = {1, 2, 3, 4} and B = {3, 4, 5}. Find A − B, A ⊕ B and |P(A)|. 2 marks
A − B = {1, 2} and B − A = {5}.
The symmetric difference is A ⊕ B = (A − B) ∪ (B − A) = {1, 2, 5}.
Since |A| = 4, the power set has |P(A)| = 2^4 = 16 subsets.
2 In a group of 50 students, 30 like tea, 25 like coffee and 10 like both. How many like neither? 2 marks
Let T and C be the tea and coffee sets. By inclusion–exclusion:
|T ∪ C| = |T| + |C| − |T ∩ C| = 30 + 25 − 10 = 45.
Students liking neither = 50 − 45 = 5.
3 Distinguish between a partition and a covering of a set, with an example. 2 marks
A covering of A is a collection of non-empty subsets whose union is A. The subsets may overlap.
A partition is a covering whose subsets are also pairwise disjoint.
For A = {1, 2, 3, 4}, {{1, 2}, {3, 4}} is a partition. {{1, 2}, {2, 3, 4}} is a covering but not a partition, because 2 lies in both blocks.
4 Define a compatibility relation and give an example. 2 marks
A compatibility relation on A is a relation that is reflexive and symmetric. It need not be transitive.
Example: on A = {1, 2, 3}, let x R y iff |x − y| ≤ 1.
- It is reflexive and symmetric.
- It is not transitive: 1 R 2 and 2 R 3, but 1 is not related to 3.
5 Define the transitive closure of a relation. Find it for R = {(1,2), (2,3)} on {1, 2, 3}. 2 marks
The transitive closure R⁺ of R is the smallest transitive relation that contains R.
Here (1,2) and (2,3) are in R, so transitivity requires (1,3). No further pairs are forced.
Therefore R⁺ = {(1,2), (2,3), (1,3)}.
6 What is a recursive function? Give a recursive definition of n! and evaluate 3!. 2 marks
A recursive function is defined by giving its value at a base case and expressing every other value in terms of values at smaller arguments.
Factorial: f(0) = 1 and f(n+1) = (n+1)·f(n).
Then f(1) = 1·1 = 1, f(2) = 2·1 = 2, and f(3) = 3·2 = 6.
10-mark questions
1 State and derive the principle of inclusion–exclusion for three finite sets using set operations. Hence find how many integers from 1 to 500 are divisible by at least one of 3, 5 or 7, and how many are divisible by none of them. 10 marks
The principle of inclusion–exclusion counts the elements of a union of finite sets without counting any element twice. It is built on the basic set operations:
- Union: A ∪ B = {x : x ∈ A ∨ x ∈ B}
- Intersection: A ∩ B = {x : x ∈ A ∧ x ∈ B}
- Difference: A − B = {x : x ∈ A ∧ x ∉ B}
- Complement: A' = U − A
Step 1: Two sets. In |A| + |B|, every element of A ∩ B is counted twice. Hence |A ∪ B| = |A| + |B| − |A ∩ B|.
Step 2: Three sets. Treat A ∪ B as a single set: |A ∪ B ∪ C| = |A ∪ B| + |C| − |(A ∪ B) ∩ C|.
By the distributive law, (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C). Also (A ∩ C) ∩ (B ∩ C) = A ∩ B ∩ C, so |(A ∪ B) ∩ C| = |A ∩ C| + |B ∩ C| − |A ∩ B ∩ C|.
Substituting both results gives |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Step 3: Set up the problem. Let A, B and C be the multiples of 3, 5 and 7 in {1, …, 500}. The number of multiples of k up to 500 is ⌊500/k⌋. A number divisible by both 3 and 5 is divisible by lcm(3, 5) = 15, and similarly for the other pairs.
- |A| = ⌊500/3⌋ = 166
- |B| = ⌊500/5⌋ = 100
- |C| = ⌊500/7⌋ = 71
- |A ∩ B| = ⌊500/15⌋ = 33
- |A ∩ C| = ⌊500/21⌋ = 23
- |B ∩ C| = ⌊500/35⌋ = 14
- |A ∩ B ∩ C| = ⌊500/105⌋ = 4
Check: 3·166 = 498, 7·71 = 497, 15·33 = 495, 21·23 = 483, 35·14 = 490 and 105·4 = 420. In each case the next multiple exceeds 500.
Step 4: Apply the formula. |A ∪ B ∪ C| = (166 + 100 + 71) − (33 + 23 + 14) + 4 = 337 − 70 + 4 = 271.
Step 5: Use the complement. The numbers divisible by none of 3, 5, 7 are |(A ∪ B ∪ C)'| = 500 − 271 = 229.
Conclusion: 271 integers from 1 to 500 are divisible by at least one of 3, 5 or 7, and 229 are divisible by none of them.
2 Let f, g : R → R be f(x) = 2x + 3 and g(x) = 3x − 1. Show that f and g are bijective, find f⁻¹, g⁻¹, g∘f and f∘g, and verify that (g∘f)⁻¹ = f⁻¹∘g⁻¹. Also, for the permutations p = (1 2 3) and q = (1 3 2 4) on {1, 2, 3, 4}, find p∘q, q∘p and p⁻¹. 10 marks
A function f : A → B assigns exactly one element of B to each element of A.
- f is one-one (injective) if f(a1) = f(a2) implies a1 = a2.
- f is onto (surjective) if every b ∈ B equals f(a) for some a.
- f is bijective if it is both, and only bijections have inverses.
Step 1: f is bijective. If 2a + 3 = 2b + 3, then a = b, so f is one-one. For any real y, take x = (y − 3)/2; then f(x) = y, so f is onto. Hence f⁻¹(y) = (y − 3)/2.
Step 2: g is bijective. If 3a − 1 = 3b − 1, then a = b. For any real y, x = (y + 1)/3 gives g(x) = y. Hence g⁻¹(y) = (y + 1)/3.
Step 3: Compositions. (g∘f)(x) = g(2x + 3) = 3(2x + 3) − 1 = 6x + 8. (f∘g)(x) = f(3x − 1) = 2(3x − 1) + 3 = 6x + 1. Since 6x + 8 ≠ 6x + 1, composition is not commutative.
Step 4: Inverse of the composition. Solving y = 6x + 8 gives (g∘f)⁻¹(y) = (y − 8)/6. On the other side: (f⁻¹∘g⁻¹)(y) = f⁻¹((y + 1)/3) = ((y + 1)/3 − 3)/2 = ((y − 8)/3)/2 = (y − 8)/6. The two agree, so (g∘f)⁻¹ = f⁻¹∘g⁻¹.
Step 5: Permutation functions. A permutation of a finite set is a bijection from the set onto itself.
- p: 1→2, 2→3, 3→1, 4→4
- q: 1→3, 3→2, 2→4, 4→1
We use (p∘q)(x) = p(q(x)), applying q first.
For p∘q:
- 1 → 3 → 1
- 2 → 4 → 4
- 3 → 2 → 3
- 4 → 1 → 2
So p∘q maps 1→1, 2→4, 3→3, 4→2, which is the cycle (2 4).
For q∘p (p applied first):
- 1 → 2 → 4
- 2 → 3 → 2
- 3 → 1 → 3
- 4 → 4 → 1
So q∘p maps 1→4, 2→2, 3→3, 4→1, which is the cycle (1 4).
Thus p∘q ≠ q∘p.
Step 6: Inverse of p. Reverse every arrow of p: p⁻¹ maps 1→3, 2→1, 3→2, 4→4, which is the cycle (1 3 2). Check: p(p⁻¹(1)) = p(3) = 1, p(p⁻¹(2)) = p(1) = 2, and so on. So p∘p⁻¹ is the identity.
Conclusion: f and g are bijections with f⁻¹(y) = (y − 3)/2 and g⁻¹(y) = (y + 1)/3. Composition of functions and of permutations is associative but not commutative. The inverse of a composite is the composite of the inverses taken in reverse order.
3 Define reflexive, irreflexive, symmetric, antisymmetric and transitive relations. For A = {1, 2, 3, 4} and R = {(1,2), (2,1), (2,3), (3,4)}, test R for these properties and find its transitive closure using Warshall's algorithm. 10 marks
A binary relation R on a set A is a subset of A × A. Its main properties are:
- Reflexive: (a,a) ∈ R for every a ∈ A.
- Irreflexive: (a,a) ∉ R for every a ∈ A.
- Symmetric: (a,b) ∈ R → (b,a) ∈ R.
- Antisymmetric: (a,b) ∈ R ∧ (b,a) ∈ R → a = b.
- Transitive: (a,b) ∈ R ∧ (b,c) ∈ R → (a,c) ∈ R.
Relations can be combined by union, intersection, complement, inverse R⁻¹ = {(b,a) : (a,b) ∈ R} and composition. The transitive closure R⁺ is the smallest transitive relation that contains R.
Step 1: Properties of R.
- Not reflexive: (1,1) ∉ R. It is irreflexive, since no pair (a,a) appears.
- Not symmetric: (2,3) ∈ R but (3,2) ∉ R.
- Not antisymmetric: (1,2) and (2,1) are both in R, but 1 ≠ 2.
- Not transitive: (1,2) and (2,3) are in R, but (1,3) is not.
Step 2: Warshall's rule. Start with W0 = M_R, the relation matrix. At stage k, update W_k[i][j] = W_(k−1)[i][j] ∨ (W_(k−1)[i][k] ∧ W_(k−1)[k][j]). In words: for every row i with a 1 in column k, and every column j with a 1 in row k, put a 1 at (i, j).
W0 W1 W2 W3 = W4
0 1 0 0 0 1 0 0 1 1 1 0 1 1 1 1
1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0Step 3: Stage-by-stage working.
- k = 1: column 1 has a 1 in row 2, and row 1 has a 1 in column 2. Add (2,2).
- k = 2: column 2 has 1s in rows 1 and 2, and row 2 has 1s in columns 1, 2 and 3. The new pairs are (1,1) and (1,3).
- k = 3: column 3 has 1s in rows 1 and 2, and row 3 has a 1 in column 4. Add (1,4) and (2,4).
- k = 4: row 4 is all zeros, so nothing changes.
Step 4: Result. R⁺ = {(1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), (2,4), (3,4)}.
Check using the digraph (arrows 1⇄2, 2→3, 3→4):
- From 1 we can reach 2, 1, 3 and 4.
- From 2 we can reach 1, 2, 3 and 4.
- From 3 we can reach only 4.
- From 4 we reach nothing.
This agrees with the final matrix.
Conclusion: R is irreflexive but is not reflexive, symmetric, antisymmetric or transitive. Warshall's algorithm, which takes O(n³) steps, gives a transitive closure containing 9 ordered pairs.
4 Show that congruence modulo 4 is an equivalence relation on Z, find its equivalence classes, and prove that the equivalence classes of any equivalence relation form a partition. Also explain how a compatibility relation leads to a covering, with an example. 10 marks
An equivalence relation is reflexive, symmetric and transitive. A partition of A is a collection of non-empty, pairwise disjoint subsets (called blocks) whose union is A. A compatibility relation is only required to be reflexive and symmetric.
Step 1: Congruence modulo 4. On Z, define a R b iff 4 | (a − b).
- Reflexive: a − a = 0 = 4·0.
- Symmetric: if a − b = 4k, then b − a = 4(−k).
- Transitive: if a − b = 4k and b − c = 4m, then a − c = 4(k + m).
Hence R is an equivalence relation.
Step 2: Equivalence classes. The class of a is [a] = {x ∈ Z : x R a}.
- [0] = {…, −8, −4, 0, 4, 8, …}
- [1] = {…, −7, −3, 1, 5, 9, …}
- [2] = {…, −6, −2, 2, 6, 10, …}
- [3] = {…, −5, −1, 3, 7, 11, …}
Every integer leaves remainder 0, 1, 2 or 3 on division by 4, so these four classes together cover Z.
Step 3: Classes form a partition (general proof).
- Each [a] contains a, so it is non-empty, and the union of all classes is A.
- Suppose [a] and [b] share an element c. Then c R a and c R b. By symmetry a R c, and by transitivity a R b.
- For any x ∈ [a], x R a and a R b give x R b, so [a] ⊆ [b]. Similarly [b] ⊆ [a].
So any two classes are either equal or disjoint, and {[0], [1], [2], [3]} is a partition of Z. Conversely, every partition defines an equivalence relation: a R b iff a and b lie in the same block.
Step 4: Compatibility relation and covering. Let A = {1, 2, 3, 4} and x C y iff |x − y| ≤ 1.
- Reflexive: |x − x| = 0.
- Symmetric: |x − y| = |y − x|.
- Not transitive: 1 C 2 and 2 C 3, but |1 − 3| = 2.
A compatibility block is a subset in which every two elements are related. A maximal compatibility block cannot be enlarged without losing this property. Here the maximal blocks are {1, 2}, {2, 3} and {3, 4}.
Their union is A, so they form a covering of A. However, 2 and 3 each appear in two blocks, so this covering is not a partition.
Conclusion: an equivalence relation splits a set into disjoint classes, which form a partition. A compatibility relation lacks transitivity, so it only produces overlapping maximal blocks, which form a covering.
5 Let D36 be the set of positive divisors of 36 with the relation 'a divides b'. Show that it is a partial order, draw its Hasse diagram, show that it is a lattice, and determine whether it is a complemented lattice. 10 marks
A partial order on A is a relation that is reflexive, antisymmetric and transitive; (A, ≤) is then called a poset. A Hasse diagram draws a poset as follows:
- smaller elements are placed lower;
- an edge is drawn only when one element covers another;
- loops, transitive edges and arrowheads are omitted.
Here D36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}.
Step 1: Divisibility is a partial order.
- Reflexive: a = a·1, so a | a.
- Antisymmetric: if a | b and b | a for positive integers, then a ≤ b and b ≤ a, so a = b.
- Transitive: if b = ak and c = bm, then c = a(km), so a | c.
Step 2: Covering pairs. b covers a when a | b and b/a is a prime, so no divisor lies strictly between them. The edges are: 1–2, 1–3, 2–4, 2–6, 3–6, 3–9, 4–12, 6–12, 6–18, 9–18, 12–36, 18–36 (12 edges in total).
The figure is a 3 × 3 grid turned into a diamond shape, with 1 at the bottom, 36 at the top and 6 in the centre.
Step 4: D36 is a lattice. For any a, b in D36, gcd(a, b) and lcm(a, b) are again divisors of 36. Under divisibility they are the greatest lower bound and the least upper bound. So a ∧ b = gcd(a, b) and a ∨ b = lcm(a, b). Examples:
- 4 ∧ 6 = 2 and 4 ∨ 6 = 12
- 12 ∧ 18 = 6 and 12 ∨ 18 = 36
- 4 ∧ 9 = 1 and 4 ∨ 9 = 36
The least element is 1 and the greatest element is 36, so the lattice is bounded.
Step 5: Complements. y is a complement of x if x ∧ y = 1 and x ∨ y = 36.
- 4 and 9 are complements of each other, and so are 1 and 36.
- 6 has no complement: gcd(6, y) = 1 forces y = 1, but lcm(6, 1) = 6 ≠ 36.
- 2 has no complement: the only candidates are 1, 3 and 9, and lcm(2, 9) = 18 ≠ 36.
- In the same way, 3, 12 and 18 have no complements.
So D36 is not complemented and is not a Boolean algebra. Like every divisor lattice, however, it is distributive.
Conclusion: (D36, |) is a poset whose Hasse diagram is a diamond-shaped 3 × 3 grid with 12 edges. It is a bounded distributive lattice with meet = gcd and join = lcm, but it is not a complemented lattice.
6 Define a lattice. Prove that every lattice satisfies the idempotent, commutative, associative and absorption laws, and that a ≤ b ⇔ a ∧ b = a ⇔ a ∨ b = b. Illustrate with the power set lattice of {a, b, c}, and show by an example that a lattice need not be distributive. 10 marks
A lattice is a poset (L, ≤) in which every pair of elements x, y has a least upper bound x ∨ y (the join) and a greatest lower bound x ∧ y (the meet). Below, letters denote elements of L.
Step 1: Example. Let S = {a, b, c}. Then (P(S), ⊆) is a lattice, with X ∨ Y = X ∪ Y and X ∧ Y = X ∩ Y.
Each singleton is joined to the two 2-element sets that contain it. The diagram has the shape of a cube, with 8 vertices and 12 edges.
Step 2: Basic laws. For all x, y, z in L:
- Idempotent: x ∨ x = x and x ∧ x = x, since the lub and glb of {x} are both x.
- Commutative: x ∨ y = y ∨ x and x ∧ y = y ∧ x, since {x, y} = {y, x}.
- Associative: (x ∨ y) ∨ z = x ∨ (y ∨ z). The left side is an upper bound of x, y and z, because x ≤ x ∨ y ≤ (x ∨ y) ∨ z, and similarly for y and z. If u is any upper bound of x, y, z, then x ∨ y ≤ u and so (x ∨ y) ∨ z ≤ u. Hence the left side is the lub of {x, y, z}. The same argument applies to the right side, so the two sides are equal. The dual argument proves the law for ∧.
- Absorption: x ∨ (x ∧ y) = x, because x ∧ y ≤ x, so the lub of x and x ∧ y is x. Dually, x ∧ (x ∨ y) = x.
Step 3: Order and operations.
- If x ≤ y, then x is a lower bound of {x, y}, and every lower bound of {x, y} is ≤ x. So x ∧ y = x.
- If x ∧ y = x, then x ∨ y = (x ∧ y) ∨ y = y by commutativity and absorption.
- If x ∨ y = y, then x ≤ x ∨ y = y.
Hence x ≤ y ⇔ x ∧ y = x ⇔ x ∨ y = y.
Step 4: Isotonicity. If y ≤ z, then x ∧ y ≤ x ∧ z and x ∨ y ≤ x ∨ z. For example, x ∧ y ≤ y ≤ z and x ∧ y ≤ x, so x ∧ y is a lower bound of x and z, and therefore x ∧ y ≤ x ∧ z.
Step 5: Distributivity can fail. Every lattice satisfies the inequality (x ∧ y) ∨ (x ∧ z) ≤ x ∧ (y ∨ z), because each of x ∧ y and x ∧ z lies below both x and y ∨ z. Equality need not hold.
Consider the diamond lattice M3 = {0, p, q, r, 1}, where p, q and r are mutually incomparable. Then:
- p ∧ (q ∨ r) = p ∧ 1 = p
- (p ∧ q) ∨ (p ∧ r) = 0 ∨ 0 = 0
Since p ≠ 0, M3 is not distributive. In contrast, P(S) is distributive, because ∩ distributes over ∪.
Conclusion: every lattice satisfies the idempotent, commutative, associative and absorption laws, together with isotonicity and the link between ≤ and ∧, ∨. Distributivity is an extra property: it holds in P(S) but fails in M3.
Combinatorics and Recurrence Relations
Syllabus: Basis of counting; Permutations; Permutations with repetitions; Circular and restricted permutations; Combinations and restricted combinations; Binomial and multinomial coefficients and theorems; Generating functions; Function of sequences; Partial fractions; Calculating coefficients of generating functions; Recurrence relations and their formulation; Solving recurrence relations by substitution and generating functions; Method of characteristic roots; Solving inhomogeneous recurrence relations
One-page revision summary
- Use the sum rule when the alternatives are disjoint, and the product rule when a task is a sequence of independent steps.
- The number of ordered arrangements of r of n distinct objects is P(n, r) = n!/(n − r)!; if repetition is allowed it is nʳ.
- Worked example: 4-digit codes made from the digits 0 to 9 number 10⁴ = 10,000 when digits may repeat, but P(10, 4) = 10 × 9 × 8 × 7 = 5040 when they may not.
- n objects with n1, n2, …, nk alike can be arranged in n!/(n1!n2!…nk!) ways.
- n distinct objects in a circle give (n − 1)! arrangements; if clockwise and anticlockwise are the same (necklace, garland), there are (n − 1)!/2.
- For restricted arrangements, treat 'together' objects as one block, and place 'never adjacent' objects in the gaps between the other objects.
- C(n, r) = n!/(r!(n − r)!), C(n, r) = C(n, n − r), and P(n, r) = r!·C(n, r).
- Restricted combinations are often easier by complement (total minus unwanted), or by first including or excluding the specified objects.
- Selecting r objects from n types with repetition, or finding non-negative integer solutions of x1 + … + xn = r, gives C(n + r − 1, r).
- Pascal's identity C(n, k) = C(n − 1, k − 1) + C(n − 1, k) builds Pascal's triangle, and ΣC(n, k) = 2ⁿ.
- Adding generating functions adds sequences, multiplying by x shifts a sequence, and multiplying two generating functions gives the convolution Σ aᵢbₙ₋ᵢ.
- Partial fractions split a rational generating function into terms like A/(1 − ax), whose coefficients A·aⁿ are read off directly.
- To count distributions, write one factor per box listing its allowed counts, multiply the factors, and extract the required coefficient.
- Formulate a recurrence by relating a problem of size n to smaller ones. Tower of Hanoi: Hₙ = 2Hₙ₋₁ + 1 with H₁ = 1, giving 2ⁿ − 1. Bit strings with no two consecutive 0s: bₙ = bₙ₋₁ + bₙ₋₂ with b₁ = 2, b₂ = 3.
- The substitution method repeatedly replaces earlier terms until the initial value appears, then sums the pattern.
- Method of characteristic roots: distinct roots give Σ cᵢrᵢⁿ, and a root of multiplicity m gives a polynomial of degree m − 1 in n multiplied by rⁿ.
- A non-homogeneous relation has solution = homogeneous solution + particular solution, and the initial conditions are applied only to this full sum.
Learn these by heart
- P(n, r) = n!/(n − r)!, C(n, r) = n!/(r!(n − r)!), circular arrangements = (n − 1)!
- Combinations with repetition: C(n + r − 1, r)
- Binomial theorem: (x + y)ⁿ = Σ C(n, k)xⁿ⁻ᵏyᵏ; multinomial coefficient n!/(n1!n2!…nm!)
- 1/(1 − ax) = Σ aⁿxⁿ and 1/(1 − x)ᵐ = Σ C(m + k − 1, k)xᵏ
- Characteristic roots: distinct r1, r2 give c1r1ⁿ + c2r2ⁿ; a double root r gives (c1 + c2n)rⁿ
- Particular solution for f(n) = bⁿ: try Cbⁿ, multiplied by nᵐ if b is a characteristic root of multiplicity m
2-mark questions
1 State the sum rule and the product rule of counting, with an example of each. 2 marks
Sum rule: if one task can be done in m ways and another in n ways, and the two cannot happen together, then one of them can be done in m + n ways.
Product rule: if a procedure has two successive steps with m and n ways, it can be done in m·n ways.
Example: with 4 maths and 3 physics books, one book can be chosen in 4 + 3 = 7 ways. One book of each subject can be chosen in 4·3 = 12 ways.
2 Find the number of distinct arrangements of the letters of the word MISSISSIPPI. 2 marks
MISSISSIPPI has 11 letters: M once, I four times, S four times and P twice.
Number of arrangements = 11!/(1!·4!·4!·2!) = 39916800/(24·24·2) = 39916800/1152 = 34650.
The formula divides by the factorials of the repeated counts, because swapping identical letters does not give a new word.
3 In how many ways can 7 persons sit around a round table? In how many ways can 7 distinct beads form a necklace? 2 marks
In a circular arrangement, rotations are treated as the same, so we fix one person and arrange the remaining 6 people in order.
Round table: (7 − 1)! = 6! = 720 ways.
A necklace can also be turned over, so clockwise and anticlockwise orders are the same.
Necklace: 720/2 = 360 ways.
4 Find the coefficient of x²y³z in the expansion of (x + y + z)⁶. 2 marks
By the multinomial theorem, the coefficient of x^a y^b z^c in (x + y + z)^n, where a + b + c = n, is n!/(a!b!c!).
Here n = 6, a = 2, b = 3 and c = 1.
Coefficient = 6!/(2!·3!·1!) = 720/12 = 60.
5 Define the ordinary generating function of a sequence. Write the generating functions of the sequences 1, 1, 1, … and 1, 2, 3, …. 2 marks
The ordinary generating function of a sequence a0, a1, a2, … is the formal power series G(x) = a0 + a1x + a2x² + … = Σ an xⁿ.
For the sequence 1, 1, 1, …, G(x) = 1 + x + x² + … = 1/(1 − x).
For the sequence 1, 2, 3, …, G(x) = 1 + 2x + 3x² + … = 1/(1 − x)².
6 What is a recurrence relation? Define its order and give an example of a linear homogeneous recurrence relation with constant coefficients. 2 marks
A recurrence relation expresses the term an of a sequence in terms of one or more earlier terms. Together with initial conditions, it fixes the whole sequence.
The order is the gap between the highest and the lowest subscripts that appear.
Example: the Fibonacci relation Fn = Fn−1 + Fn−2 with F0 = 0 and F1 = 1. It is linear, homogeneous, has constant coefficients and is of order 2.
10-mark questions
1 Derive the formula for the number of r-permutations of n distinct objects. Using it, find the number of ways to arrange the letters of the word COMPUTER when (i) there is no restriction, (ii) the three vowels are always together, (iii) no two vowels are adjacent, and (iv) the word begins with C and ends with R. Also find the number of circular arrangements of these 8 letters. 10 marks
A permutation is an ordered arrangement of objects. P(n, r) denotes the number of ordered arrangements of r objects chosen from n distinct objects. It follows directly from the product rule.
Derivation:
- Step 1: The first position can be filled in n ways.
- Step 2: After one object is used, the second position can be filled in n − 1 ways.
- Step 3: Continuing in the same way, the r-th position can be filled in n − r + 1 ways.
- Step 4: By the product rule, P(n, r) = n(n − 1)(n − 2)…(n − r + 1) = n!/(n − r)!.
- Step 5: When r = n, P(n, n) = n!, since 0! = 1.
The word COMPUTER has 8 distinct letters. The vowels are O, U and E (3 letters). The consonants are C, M, P, T and R (5 letters).
(i) No restriction: 8! = 40320.
(ii) Vowels together:
- Tie O, U and E into one block.
- We now arrange 5 consonants and 1 block, which is 6 units, in 6! = 720 ways.
- Inside the block the vowels can be arranged in 3! = 6 ways.
- Total = 720 × 6 = 4320.
(iii) No two vowels adjacent (gap method):
- Arrange the 5 consonants first in 5! = 120 ways.
- This creates 6 gaps: _ C _ M _ P _ T _ R _.
- Place the 3 distinct vowels in 3 different gaps in P(6, 3) = 6·5·4 = 120 ways.
- Total = 120 × 120 = 14400.
(iv) Begins with C and ends with R:
- The first and last positions are fixed.
- The remaining 6 letters fill the 6 middle positions in 6! = 720 ways.
Circular arrangement:
- Picture 8 seats around a circle.
- All rotations of one arrangement are the same, so we fix one letter in a seat.
- The other 7 letters are arranged in 7! = 5040 ways.
- In general, n distinct objects in a circle give (n − 1)! arrangements.
Conclusion: the answers are 40320, 4320, 14400, 720 and 5040. Restricted problems are handled by blocking objects together, by placing objects in gaps, or by fixing positions, and then applying the product rule.
2 Explain combinations and combinations with repetition. A committee of 5 is to be formed from 6 men and 4 women. In how many ways can it be formed if (i) there is no restriction, (ii) it has exactly 2 women, (iii) it has at least one woman, and (iv) a particular man must be included and a particular woman must be excluded? Also find the number of ways to select 10 fruits from 4 kinds of fruit (unlimited supply of each), and the number of such selections containing at least one fruit of each kind. 10 marks
A combination is a selection in which order does not matter. The number of r-subsets of n distinct objects is C(n, r) = n!/(r!(n − r)!). Each subset can be ordered in r! ways, so P(n, r) = r!·C(n, r).
When repetition is allowed, choosing r objects from n types is the same as placing r stars and n − 1 bars in a row. This gives C(n + r − 1, r) selections.
Committee problem (6 men, 4 women, 10 people in all):
(i) No restriction: C(10, 5) = 252.
(ii) Exactly 2 women:
- Choose 2 of the 4 women and 3 of the 6 men.
- C(4, 2)·C(6, 3) = 6 × 20 = 120.
(iii) At least one woman:
- Use the complement: subtract the all-men committees from the total.
- All-men committees = C(6, 5) = 6.
- Answer = 252 − 6 = 246.
(iv) Particular man included and particular woman excluded:
- The chosen man fills one seat, and the excluded woman leaves the pool.
- Choose the remaining 4 members from 10 − 2 = 8 people.
- C(8, 4) = 70.
Fruit selection (n = 4 kinds, r = 10 fruits):
Step 1: Let x1 + x2 + x3 + x4 = 10, where each xi ≥ 0 is the number of fruits of kind i. Each solution is one selection.
Step 2: Stars and bars: 10 stars and 3 bars in a row. The number of arrangements is C(13, 3) = (13·12·11)/6 = 286.
Step 3: For at least one of each kind, first give one fruit of each kind. The remaining 6 fruits are chosen freely: C(4 + 6 − 1, 6) = C(9, 3) = 84.
Conclusion: the committee answers are 252, 120, 246 and 70. The fruit selections number 286, of which 84 contain every kind. Complements and pre-allocation are the standard tools for restricted combinations.
3 State and prove the binomial theorem. Deduce that ΣC(n, k) = 2ⁿ and Σ(−1)ᵏC(n, k) = 0. State the multinomial theorem. Find (a) the coefficient of x⁴ in (1 + 2x)⁶ and (b) the coefficient of a²b²c² in (a + b + c)⁶. 10 marks
The binomial theorem gives the expansion of a power of a two-term sum. The numbers C(n, k) that appear are called binomial coefficients.
Statement: for every non-negative integer n,
(x + y)ⁿ = Σ (k = 0 to n) C(n, k) xⁿ⁻ᵏ yᵏ.
Combinatorial proof:
- Step 1: (x + y)ⁿ = (x + y)(x + y)…(x + y), with n factors.
- Step 2: Expanding means picking either x or y from each factor and multiplying the picks.
- Step 3: The term xⁿ⁻ᵏyᵏ appears exactly when y is picked from k of the n factors and x from the rest.
- Step 4: The k factors can be chosen in C(n, k) ways, so the coefficient of xⁿ⁻ᵏyᵏ is C(n, k).
The coefficients satisfy Pascal's identity C(n, k) = C(n − 1, k − 1) + C(n − 1, k). This builds Pascal's triangle.
Deductions:
- Put x = y = 1: ΣC(n, k) = (1 + 1)ⁿ = 2ⁿ. This is the number of subsets of an n-set.
- Put x = 1 and y = −1: Σ(−1)ᵏC(n, k) = (1 − 1)ⁿ = 0 for n ≥ 1. So the even-sized and odd-sized subsets are equal in number.
Multinomial theorem:
(x1 + x2 + … + xm)ⁿ = Σ [n!/(n1!n2!…nm!)] x1^n1 x2^n2 … xm^nm.
The sum runs over all non-negative integers with n1 + … + nm = n. The proof is the same: we pick x1 from n1 factors, x2 from n2 factors, and so on. The number of ways is n!/(n1!…nm!).
(a) Coefficient of x⁴ in (1 + 2x)⁶:
- The general term is C(6, k)(2x)ᵏ.
- Take k = 4: C(6, 4)·2⁴ = 15 × 16 = 240.
(b) Coefficient of a²b²c² in (a + b + c)⁶:
- Here n1 = n2 = n3 = 2.
- Coefficient = 6!/(2!2!2!) = 720/8 = 90.
Conclusion: the binomial theorem counts choices of factors, and the multinomial theorem extends it to m terms. In the examples, the required coefficients are 240 and 90.
4 Define the generating function of a sequence and list some standard generating functions. Using partial fractions, find the sequence whose generating function is 1/((1 − x)(1 − 2x)). Also, using generating functions, find the number of ways to distribute 12 identical balls into 4 distinct boxes so that every box receives at least 2 balls. 10 marks
The generating function of a sequence a0, a1, a2, … is G(x) = Σ an xⁿ. It turns a counting problem about sequences into algebra on power series. Then an is simply the coefficient of xⁿ.
Standard results:
- 1/(1 − x) = 1 + x + x² + …
- 1/(1 − ax) = Σ aⁿxⁿ
- 1/(1 − x)ᵐ = Σ C(m + k − 1, k)xᵏ
- (1 − x^(r+1))/(1 − x) = 1 + x + … + x^r
- Multiplying G(x) by x shifts the sequence one place to the right.
Part 1: partial fractions.
Step 1: Write 1/((1 − x)(1 − 2x)) = A/(1 − x) + B/(1 − 2x). So 1 = A(1 − 2x) + B(1 − x).
Step 2: Put x = 1: 1 = A(−1), so A = −1.
Step 3: Put x = 1/2: 1 = B(1/2), so B = 2.
Step 4: G(x) = 2/(1 − 2x) − 1/(1 − x) = Σ (2·2ⁿ − 1)xⁿ.
Hence an = 2ⁿ⁺¹ − 1, giving the sequence 1, 3, 7, 15, …
Check: the product of the two series gives an = 1 + 2 + … + 2ⁿ = 2ⁿ⁺¹ − 1, which agrees.
Part 2: distributing the balls.
Step 1: Each box gets at least 2 balls. So the generating function for one box is x² + x³ + x⁴ + … = x²/(1 − x).
Step 2: The boxes are independent, so we multiply the four factors: G(x) = x⁸/(1 − x)⁴.
Step 3: The coefficient of x¹² in G(x) equals the coefficient of x⁴ in (1 − x)⁻⁴. That is C(4 + 4 − 1, 4) = C(7, 4) = 35.
Step 4: Check: put yi = xi − 2. Then y1 + y2 + y3 + y4 = 4 with yi ≥ 0, which has C(7, 3) = 35 solutions. This agrees.
Conclusion: partial fractions split a rational generating function into geometric series, which gives an = 2ⁿ⁺¹ − 1. Products of generating functions count combined choices, which gives 35 distributions.
5 Solve the recurrence relation aₙ = 5aₙ₋₁ − 6aₙ₋₂ for n ≥ 2, with a₀ = 2 and a₁ = 5, using generating functions. Verify the answer by the method of characteristic roots, and explain how that method handles distinct and repeated roots. 10 marks
A linear recurrence with constant coefficients can be solved by turning it into an equation for its generating function A(x) = Σ aₙxⁿ. It can also be solved through the roots of its characteristic equation.
Part 1: generating function method.
Step 1: Multiply the recurrence by xⁿ and sum for n ≥ 2:
Σ aₙxⁿ = 5x Σ aₙ₋₁xⁿ⁻¹ − 6x² Σ aₙ₋₂xⁿ⁻².
Step 2: Write each sum in terms of A(x):
A(x) − a₀ − a₁x = 5x(A(x) − a₀) − 6x²A(x).
Step 3: Collect the A(x) terms:
A(x)(1 − 5x + 6x²) = a₀ + a₁x − 5a₀x = 2 + 5x − 10x = 2 − 5x.
Step 4: Factor the denominator: A(x) = (2 − 5x)/((1 − 2x)(1 − 3x)).
Step 5: Use partial fractions: 2 − 5x = P(1 − 3x) + Q(1 − 2x).
- Put x = 1/3: 1/3 = Q/3, so Q = 1.
- Put x = 1/2: −1/2 = −P/2, so P = 1.
Step 6: A(x) = 1/(1 − 2x) + 1/(1 − 3x). Therefore aₙ = 2ⁿ + 3ⁿ.
Part 2: method of characteristic roots.
Step 1: Substitute aₙ = rⁿ to get r² − 5r + 6 = 0, so (r − 2)(r − 3) = 0.
Step 2: The roots 2 and 3 are distinct. So the general solution is aₙ = A·2ⁿ + B·3ⁿ.
Step 3: Apply the initial conditions: A + B = 2 and 2A + 3B = 5. This gives B = 1 and A = 1.
Step 4: So aₙ = 2ⁿ + 3ⁿ, the same answer.
Check: a₂ = 5(5) − 6(2) = 13, and the formula gives 4 + 9 = 13.
Cases of the characteristic method:
- Distinct roots r1, …, rk: aₙ = c1·r1ⁿ + … + ck·rkⁿ.
- A root r of multiplicity m contributes (c0 + c1n + … + c(m−1)n^(m−1))rⁿ.
- For example, a double root 2 contributes (A + Bn)2ⁿ.
- The constants are always fixed by the initial conditions.
Conclusion: both methods give aₙ = 2ⁿ + 3ⁿ. The generating function method also explains why the roots appear: they are the reciprocals of the roots of the denominator 1 − 5x + 6x² = (1 − 2x)(1 − 3x), whose roots are x = 1/2 and x = 1/3.
6 (a) Solve aₙ = aₙ₋₁ + n for n ≥ 1, with a₀ = 1, by the substitution (iteration) method. (b) Explain the method for solving non-homogeneous linear recurrence relations, and solve aₙ − 4aₙ₋₁ + 4aₙ₋₂ = 3ⁿ for n ≥ 2, with a₀ = 10 and a₁ = 31. 10 marks
Some recurrences can be solved by repeatedly substituting the relation into itself. Linear recurrences with a non-zero right-hand side need a homogeneous part and a particular part.
Part (a): substitution.
Step 1: aₙ = aₙ₋₁ + n = aₙ₋₂ + (n − 1) + n = aₙ₋₃ + (n − 2) + (n − 1) + n.
Step 2: Continuing down to a₀ gives aₙ = a₀ + (1 + 2 + … + n).
Step 3: aₙ = 1 + n(n + 1)/2.
Check: a₁ = 2 and a₂ = 4. These agree with 1 + 1 = 2 and 2 + 2 = 4.
Part (b): non-homogeneous recurrences.
For aₙ + c1aₙ₋₁ + … + ckaₙ₋ₖ = f(n), the general solution is aₙ = aₙ^(h) + aₙ^(p).
- aₙ^(h) is the solution of the homogeneous relation, found from the characteristic roots.
- aₙ^(p) is any one particular solution.
Trial forms for the particular solution:
- If f(n) is a constant, try C.
- If f(n) is a polynomial of degree d, try a general polynomial of degree d.
- If f(n) = bⁿ, try C·bⁿ. If b is a characteristic root of multiplicity m, multiply the trial by nᵐ.
The constants of the homogeneous part are found only after adding the particular solution.
Solution:
Step 1: Homogeneous part. r² − 4r + 4 = 0 gives r = 2 twice. So aₙ^(h) = (A + Bn)2ⁿ.
Step 2: Particular part. Since 3 is not a root, try aₙ = C·3ⁿ:
C·3ⁿ − 4C·3ⁿ⁻¹ + 4C·3ⁿ⁻² = 3ⁿ.
Divide by 3ⁿ⁻²: 9C − 12C + 4C = 9, so C = 9.
Step 3: General solution: aₙ = (A + Bn)2ⁿ + 9·3ⁿ.
Step 4: Initial conditions.
- n = 0: A + 9 = 10, so A = 1.
- n = 1: 2(1 + B) + 27 = 31, so B = 1.
Step 5: aₙ = (n + 1)2ⁿ + 9·3ⁿ.
Check: the recurrence gives a₂ = 4(31) − 4(10) + 9 = 93. The formula gives 3·4 + 81 = 93.
Conclusion: by substitution, aₙ = 1 + n(n + 1)/2. The non-homogeneous recurrence has solution aₙ = (n + 1)2ⁿ + 9·3ⁿ.
Graph Theory
Syllabus: Basic concepts of graphs; Graph theory and its applications; Subgraphs; Graph representations: adjacency and incidence matrices; Isomorphic graphs; Paths and circuits; Eulerian and Hamiltonian graphs
One-page revision summary
- A graph G = (V, E) is a set of vertices with edges joining pairs of them; the degree of a vertex counts its incident edges, with a loop counting twice.
- Simple graphs have no loops or parallel edges, multigraphs allow parallel edges, and pseudographs allow both loops and parallel edges.
- Kn is the complete graph with n(n-1)/2 edges, Km,n is the complete bipartite graph with mn edges, and in a k-regular graph every degree is k.
- Graph theory models networks, routing, scheduling via colouring, deadlock detection, web links, compilers and circuit layouts.
- A subgraph uses a subset of vertices and edges; a spanning subgraph keeps all vertices; an induced subgraph keeps every edge among the chosen vertices.
- G - v removes a vertex and all edges on it, while G - e removes only one edge.
- The adjacency matrix of an undirected graph is symmetric, and its row sums give the degrees.
- Every column of an incidence matrix contains exactly two 1s, because each edge has two end vertices.
- The (i, j) entry of A^k counts the walks of length k from vi to vj.
- Isomorphic graphs share vertex count, edge count, degree sequence, connectivity and cycle structure; to prove isomorphism you must exhibit an edge-preserving bijection.
- Equal degree sequences do not guarantee isomorphism: C6 and two disjoint triangles both have all degrees 2.
- In a walk, vertices and edges may repeat; in a path, no vertex repeats; a circuit is a closed walk with no repeated edge.
- A graph is connected if a path exists between every pair of its vertices.
- A connected graph has an Euler circuit if and only if every vertex has even degree.
- The Königsberg bridges have no Euler path because all four land areas have odd degree.
- Dirac's and Ore's theorems give sufficient, but not necessary, conditions for a graph to be Hamiltonian.
- Eulerian and Hamiltonian properties are independent: K4 is Hamiltonian but not Eulerian, and the bow-tie graph is Eulerian but not Hamiltonian.
Learn these by heart
- Handshaking theorem: Σ deg(v) = 2|E|, so the number of odd-degree vertices is always even.
- Number of edges: |E(Kn)| = n(n-1)/2 and |E(Km,n)| = mn.
- Euler circuit exists if and only if the graph is connected and all degrees are even; Euler path (not a circuit) exists if and only if it is connected with exactly 2 odd vertices.
- Dirac's theorem: n ≥ 3 and deg(v) ≥ n/2 for all v implies G is Hamiltonian.
- Ore's theorem: n ≥ 3 and deg(u) + deg(v) ≥ n for every non-adjacent pair u, v implies G is Hamiltonian.
- G1 ≅ G2 if and only if there is a bijection f with uv ∈ E(G1) ⇔ f(u)f(v) ∈ E(G2).
- The (i, j) entry of A^k is the number of walks of length k from vi to vj.
2-mark questions
1 State the handshaking theorem. Use it to find the number of edges in a graph with 6 vertices, each of degree 3. 2 marks
Handshaking theorem: in any undirected graph G = (V, E), Σ deg(v) = 2|E|. This holds because each edge adds 1 to the degree of each of its two end vertices.
Here Σ deg(v) = 6 × 3 = 18.
So |E| = 18/2 = 9 edges.
2 Define a subgraph and a spanning subgraph. 2 marks
A graph H = (V', E') is a subgraph of G = (V, E) if V' ⊆ V, E' ⊆ E, and every edge in E' has both its end vertices in V'.
H is a spanning subgraph if it contains every vertex of G, that is V' = V. Its edge set E' may be any subset of E.
3 Write the adjacency matrix of the complete graph K3 and state two of its properties. 2 marks
Label the vertices v1, v2, v3. Every pair is adjacent, so the rows of A are:
0 1 1
1 0 1
1 1 0Properties:
- A is symmetric and its diagonal is zero, because there are no loops.
- Each row sum is 2, the degree of that vertex.
4 When are two graphs said to be isomorphic? Name three invariants they must share. 2 marks
G1 and G2 are isomorphic if there is a bijection f: V(G1) → V(G2) such that u and v are adjacent in G1 exactly when f(u) and f(v) are adjacent in G2.
Isomorphic graphs must have:
- the same number of vertices,
- the same number of edges,
- the same degree sequence.
5 Distinguish between a walk, a path and a circuit in a graph. 2 marks
- A walk is an alternating sequence of vertices and edges, where each edge joins the vertices on either side of it. Repetition is allowed.
- A path is a walk in which no vertex, and hence no edge, is repeated.
- A circuit is a closed walk (it starts and ends at the same vertex) in which no edge is repeated.
6 Is the complete graph K4 Eulerian? Is it Hamiltonian? Justify briefly. 2 marks
Eulerian: every vertex of K4 has degree 3, which is odd. A connected graph has an Euler circuit only if all its degrees are even, so K4 is not Eulerian. With four odd vertices it has no Euler path either.
Hamiltonian: yes. The cycle v1-v2-v3-v4-v1 visits every vertex exactly once.
10-mark questions
1 Define a graph. Explain the following types of graphs with an example of each: simple graph, multigraph, pseudograph, directed graph, complete graph, regular graph, bipartite graph and null graph. Also discuss the applications of graph theory in computer science. 10 marks
A graph G = (V, E) consists of a non-empty set V of vertices and a set E of edges. Each edge joins a pair of vertices, called its end points. Graphs model any system of objects connected by relationships.
Basic terms:
- Two vertices are adjacent if an edge joins them; that edge is incident on both.
- The degree deg(v) is the number of edges incident on v. A loop counts twice.
- A vertex of degree 0 is isolated; a vertex of degree 1 is pendant.
Types of graphs: 1. Simple graph: no loops and no parallel edges. Example: a triangle on a, b, c. 2. Multigraph: parallel edges are allowed but loops are not. Example: two separate edges both joining a and b. 3. Pseudograph: both loops and parallel edges are allowed. Example: a loop at a together with an edge ab. 4. Directed graph (digraph): each edge is an ordered pair (u, v), drawn as an arrow from u to v. Each vertex has an in-degree and an out-degree. 5. Complete graph Kn: a simple graph in which every pair of distinct vertices is adjacent. It has n(n-1)/2 edges, so K4 has 4·3/2 = 6 edges. 6. Regular graph: every vertex has the same degree k (a k-regular graph). The cycle C5 is 2-regular and K4 is 3-regular. 7. Bipartite graph: V can be split into disjoint sets V1 and V2 so that every edge joins V1 to V2. The complete bipartite graph Km,n has mn edges, so K2,3 has 6 edges. 8. Null graph Nn: n vertices and no edges.
Diagrams in words:
- K2,3: place two vertices on top and three below, and join every top vertex to every bottom vertex.
Applications in computer science:
- Networks: routers are vertices and links are edges. Shortest-path algorithms choose routes.
- Data structures and compilers: trees, heaps and adjacency lists are graphs. Control-flow graphs drive code optimisation.
- Web and social networks: pages or users are vertices, and hyperlinks or friendships are edges. Page ranking uses this link structure.
- Scheduling and register allocation: graph colouring gives conflicting tasks or variables different slots.
- Operating systems: a cycle in a resource-allocation graph signals possible deadlock.
- Routing and circuit design: road maps, the travelling-salesman problem and VLSI wiring layouts.
In conclusion, each type of graph places different restrictions on edges. This flexibility makes graph theory a basic modelling tool throughout computer science.
2 Define subgraph, spanning subgraph, induced subgraph, vertex-deleted subgraph and edge-deleted subgraph, illustrating each with an example. State and prove the handshaking theorem, and deduce that every graph has an even number of vertices of odd degree. 10 marks
Subgraphs let us study a part of a graph, and the handshaking theorem links the degrees of vertices to the number of edges. Both are basic tools used throughout graph theory.
Example graph G: V = {a, b, c, d}, E = {ab, bc, cd, da, ac}. In words, G is a square a-b-c-d with the diagonal ac.
Types of subgraphs: 1. Subgraph: H = (V', E') with V' ⊆ V and E' ⊆ E, where every edge of E' has both ends in V'. Example: V' = {a, b, c}, E' = {ab}. 2. Spanning subgraph: contains all vertices of G. Example: V' = V, E' = {ab, bc, cd}. This is a path through all four vertices. 3. Induced subgraph G[S]: takes vertex set S and every edge of G whose ends both lie in S. Example: G[{a, b, c}] has edges ab, bc, ac, which form a triangle. 4. Vertex-deleted subgraph G - v: remove v and all edges incident on it. Example: G - c has vertices a, b, d and edges ab, da. 5. Edge-deleted subgraph G - e: remove only the edge e. Example: G - ac is the 4-cycle a-b-c-d-a.
Handshaking theorem: for any undirected graph G = (V, E), Σ deg(v) = 2|E|.
Proof: 1. Take any edge e = uv with u ≠ v. It adds 1 to deg(u) and 1 to deg(v), so it contributes 2 to the total degree. 2. A loop at u adds 2 to deg(u), so it also contributes 2. 3. Every edge therefore contributes exactly 2 to Σ deg(v). 4. Summing over all edges gives Σ deg(v) = 2|E|.
Corollary: the number of odd-degree vertices is even. 1. Split V into V_even (vertices of even degree) and V_odd (vertices of odd degree). 2. Then 2|E| = Σ_{V_even} deg(v) + Σ_{V_odd} deg(v). 3. The left side is even, and the first sum is a sum of even numbers, so it is even. 4. Hence Σ_{V_odd} deg(v) is even. 5. A sum of odd numbers is even only when there is an even count of them. So |V_odd| is even.
Verification on G:
- Degrees: deg(a) = 3, deg(b) = 2, deg(c) = 3, deg(d) = 2.
- Sum = 10 = 2 × 5, matching the five edges.
- The odd vertices are a and c, which is an even count of 2.
In conclusion, subgraphs let us isolate parts of a graph, and the handshaking theorem is a quick check that any proposed degree sequence must satisfy.
3 Explain the adjacency matrix and the incidence matrix of an undirected graph. For the graph G with V = {a, b, c, d} and edges e1 = ab, e2 = bc, e3 = cd, e4 = da, e5 = ac, write both matrices and state their properties. Use A² to find the number of walks of length 2 between b and d. 10 marks
A graph can be stored in a computer as a matrix. The two standard choices are the adjacency matrix and the incidence matrix.
1. Adjacency matrix: for n vertices v1, ..., vn, A is the n × n matrix with aij = number of edges joining vi and vj. For a simple graph, aij = 1 if vi and vj are adjacent and 0 otherwise.
2. Incidence matrix: for n vertices and m edges, M is the n × m matrix with mij = 1 if vertex vi is an end of edge ej and 0 otherwise.
3. Adjacency matrix of G (row and column order a, b, c, d):
a b c d
a [ 0 1 1 1 ]
b [ 1 0 1 0 ]
c [ 1 1 0 1 ]
d [ 1 0 1 0 ]4. Incidence matrix of G (rows a, b, c, d; columns e1 to e5):
e1 e2 e3 e4 e5
a [ 1 0 0 1 1 ]
b [ 1 1 0 0 0 ]
c [ 0 1 1 0 1 ]
d [ 0 0 1 1 0 ]5. Properties:
- A is symmetric, and its diagonal is zero when there are no loops.
- Each row sum of A gives the degree: a = 3, b = 2, c = 3, d = 2.
- Every column of M has exactly two 1s, because each edge has two ends.
- Each row sum of M is also the degree. The total of all entries of M is 10 = 2 × 5, which agrees with the handshaking theorem.
6. Counting walks: the (i, j) entry of A^k is the number of walks of length k from vi to vj. For k = 2, the (i, j) entry equals the number of common neighbours of vi and vj.
The neighbour sets are:
- N(a) = {b, c, d}
- N(b) = {a, c}
- N(c) = {a, b, d}
- N(d) = {a, c}
Computing each entry from these sets gives:
a b c d
a [ 3 1 2 1 ]
b [ 1 2 1 2 ]
c [ 2 1 3 1 ]
d [ 1 2 1 2 ]7. Walks from b to d: the (b, d) entry is |{a, c} ∩ {a, c}| = 2. The two walks are b-a-d and b-c-d.
As a check, the diagonal of A² equals the degrees (3, 2, 3, 2). This is because a walk of length 2 from a vertex back to itself goes out along an edge and returns along the same edge.
In conclusion, the adjacency matrix suits fast adjacency tests and walk counting. The incidence matrix records how vertices relate to edges and makes the degree-sum property easy to see.
4 Define isomorphism of graphs and list the invariants that isomorphic graphs must share. Determine whether G1 and G2 are isomorphic, where G1 has vertices u1 to u5 and edges u1u2, u2u3, u3u4, u4u5, u5u1, u1u3, and G2 has vertices v1 to v5 and edges v1v2, v2v3, v3v4, v4v5, v5v1, v2v5. Also give two graphs with the same degree sequence that are not isomorphic. 10 marks
Two graphs may be drawn very differently yet have the same structure. Isomorphism makes this idea precise.
Definition: G1 and G2 are isomorphic (G1 ≅ G2) if there is a bijection f: V(G1) → V(G2) such that u and v are adjacent in G1 if and only if f(u) and f(v) are adjacent in G2. Equivalently, after a suitable reordering of vertices, the two graphs have identical adjacency matrices.
Invariants (necessary conditions):
- same number of vertices and edges;
- same degree sequence;
- same number of connected components;
- same number of cycles of each length;
- degrees of adjacent vertices must correspond.
These conditions are necessary but not sufficient. To prove isomorphism, an explicit bijection must be exhibited.
Solving the given problem:
1. Counts: both graphs have 5 vertices and 6 edges.
2. Degrees in G1: u1 has neighbours u2, u5, u3, so degree 3. u3 has neighbours u2, u4, u1, so degree 3. u2, u4 and u5 have degree 2. The degree sequence is (3, 3, 2, 2, 2).
3. Degrees in G2: v2 has neighbours v1, v3, v5, so degree 3. v5 has neighbours v4, v1, v2, so degree 3. v1, v3 and v4 have degree 2. The degree sequence is (3, 3, 2, 2, 2).
4. Structure: in each graph the two degree-3 vertices are adjacent (u1u3 and v2v5). They have exactly one common neighbour: u2 in G1 and v1 in G2.
5. Proposed mapping:
- f(u1) = v2 and f(u3) = v5;
- f(u2) = v1, matching the common neighbours;
- u4 is adjacent to u3, so f(u4) = v4, since v4 is adjacent to v5;
- f(u5) = v3.
6. Edge check:
- u1u2 → v2v1 ✓
- u2u3 → v1v5 ✓
- u3u4 → v5v4 ✓
- u4u5 → v4v3 ✓
- u5u1 → v3v2 ✓
- u1u3 → v2v5 ✓
All 6 edges map to distinct edges of G2, and G2 has exactly 6 edges. So adjacency is preserved in both directions, and G1 ≅ G2.
Non-isomorphic graphs with the same degree sequence:
- Take the 6-cycle C6, and a graph made of two disjoint triangles.
- Both have 6 vertices, 6 edges and every degree equal to 2.
- C6 is connected, while the other graph has two components. So they are not isomorphic.
In conclusion, matching invariants is only a first filter. A correct, edge-preserving bijection is what proves that two graphs are isomorphic.
5 State and prove Euler's theorem on the existence of an Euler circuit in a connected graph. State the condition for an Euler path. Apply these results to the Königsberg bridge problem, and find an Euler path in the graph with edges ab, bc, cd, da, ac. 10 marks
An Euler path uses every edge of a graph exactly once. An Euler circuit is an Euler path that starts and ends at the same vertex. A graph that has an Euler circuit is called Eulerian.
Theorem: a connected graph G (with at least one edge) has an Euler circuit if and only if every vertex has even degree.
Proof of necessity (if Eulerian, then all degrees are even): 1. Trace the Euler circuit. 2. Each time the circuit passes through a vertex, it enters on one edge and leaves on another, using 2 edges at that vertex. 3. The start vertex is left once at the beginning and entered once at the end, which is again 2 edges. 4. Every edge is used exactly once, so every degree is a multiple of 2.
Proof of sufficiency (if all degrees are even, then Eulerian): 1. Start at any vertex v and walk along unused edges, never repeating an edge. 2. Whenever the walk enters a vertex w ≠ v, it has used an odd number of w's edges. Since deg(w) is even, an unused edge remains, so the walk can continue. Hence the walk can only get stuck at v, and it forms a closed circuit C. 3. If C uses every edge, we are done. 4. Otherwise, because G is connected, some vertex w on C still has unused edges. 5. Removing the edges of C reduces each degree by an even number, so all degrees remain even. Starting at w, build a second circuit C' from the unused edges in the same way. 6. Splice C' into C at w to obtain a longer circuit. 7. Repeat until no edges remain. The final circuit is an Euler circuit.
Euler path condition: a connected graph has an Euler path that is not a circuit if and only if it has exactly two vertices of odd degree. The path must start at one of them and end at the other.
Königsberg bridge problem:
- Represent the four land areas (two river banks and two islands) as vertices and the seven bridges as edges.
- The degrees are 5, 3, 3 and 3, so all four vertices are odd.
- Since there are four odd vertices, neither an Euler circuit nor an Euler path exists.
- Therefore no walk can cross every bridge exactly once.
Worked example: edges ab, bc, cd, da, ac. 1. Degrees: a = 3, b = 2, c = 3, d = 2. 2. Exactly two vertices (a and c) are odd, so an Euler path exists from a to c, but there is no Euler circuit. 3. A valid path is a-b-c-d-a-c. It uses ab, bc, cd, da, ac, each exactly once.
In conclusion, Euler's theorem reduces the question of traversing every edge to simply checking the parity of the degrees.
6 Define Hamiltonian path, Hamiltonian circuit and Hamiltonian graph. State Dirac's and Ore's theorems. Show with examples that a graph may be Eulerian but not Hamiltonian, and Hamiltonian but not Eulerian. Compare Eulerian and Hamiltonian graphs. 10 marks
Eulerian problems are about traversing every edge, while Hamiltonian problems are about visiting every vertex. The two ideas look similar but behave very differently.
Definitions: 1. Hamiltonian path: a path that visits every vertex exactly once. 2. Hamiltonian circuit: a cycle that visits every vertex exactly once and returns to its start. 3. Hamiltonian graph: a graph that contains a Hamiltonian circuit.
Sufficient conditions (n ≥ 3, simple graph): 1. Dirac's theorem: if deg(v) ≥ n/2 for every vertex v, then G is Hamiltonian. 2. Ore's theorem: if deg(u) + deg(v) ≥ n for every pair of non-adjacent vertices u and v, then G is Hamiltonian.
Dirac's theorem is a special case of Ore's theorem. Neither condition is necessary: the cycle C6 is Hamiltonian even though every vertex has degree 2 < 3.
Applying the theorems:
- In K3,3 we have n = 6 and every degree is 3 ≥ 6/2, so K3,3 is Hamiltonian by Dirac.
- In Kn (n ≥ 3) every degree is n - 1 ≥ n/2, so Kn is Hamiltonian.
A non-Hamiltonian graph, K2,3:
- Every cycle in a bipartite graph alternates between the two sides. So a Hamiltonian cycle needs both sides to have equal size.
- Here the sides have 2 and 3 vertices, so K2,3 has no Hamiltonian circuit.
- It does have a Hamiltonian path. With sides {a1, a2} and {b1, b2, b3}, the path b1-a1-b2-a2-b3 works.
Eulerian but not Hamiltonian, the bow-tie graph:
- Take two triangles a-b-c and c-d-e that share the vertex c.
- The degrees are 2, 2, 4, 2, 2, all even, and the graph is connected, so it is Eulerian. One Euler circuit is c-a-b-c-d-e-c.
- Any Hamiltonian circuit would have to pass through c twice to reach both triangles. So the graph is not Hamiltonian.
Hamiltonian but not Eulerian, K4:
- The cycle v1-v2-v3-v4-v1 is a Hamiltonian circuit.
- Every degree is 3, which is odd, so K4 has no Euler circuit.
Comparison:
- Eulerian: every edge is used exactly once (vertices may repeat). Hamiltonian: every vertex is visited exactly once (edges may be unused).
- Eulerian: there is a simple necessary and sufficient test, namely connected with all degrees even. Hamiltonian: no simple characterisation is known; there are only sufficient conditions such as those of Dirac and Ore.
- Eulerian: an Euler circuit can be found efficiently. Hamiltonian: deciding whether a graph is Hamiltonian is NP-complete.
- Applications: Euler circuits suit route inspection, such as mail delivery along every street. Hamiltonian circuits underlie the travelling-salesman problem.
In conclusion, the two properties are independent of each other. Euler circuits are easy to recognise, while Hamiltonian circuits are hard to find in general.
Multigraphs
Syllabus: Multigraphs; Bipartite graphs; Planar graphs; Euler's theorem; Graph colouring and covering; Chromatic number; Spanning trees; Prim's and Kruskal's algorithms; BFS and DFS spanning trees
One-page revision summary
- A multigraph allows parallel edges between the same pair of vertices; a pseudograph also allows loops.
- The handshaking lemma holds in multigraphs: the sum of all degrees equals 2e, with each loop adding 2.
- Euler's circuit theorem: a connected multigraph has an Euler circuit if and only if every vertex has even degree, and an Euler path if and only if exactly 0 or 2 vertices have odd degree.
- A graph is bipartite if its vertices split into two sets with every edge going across; Km,n has m + n vertices and mn edges.
- A graph is bipartite if and only if it has no odd cycle, and this can be tested by BFS level parity.
- A planar graph can be drawn without edge crossings, and a drawing divides the plane into faces, exactly one of which is unbounded.
- Euler's formula v − e + f = 2 holds for every connected planar graph, including multigraphs.
- K5 and K3,3 are non-planar, and Kuratowski's theorem says a graph is planar if and only if it contains no subdivision of either.
- A proper colouring gives adjacent vertices different colours; the four colour theorem says every planar graph has χ ≤ 4.
- Covering: a vertex cover touches every edge, an edge cover touches every vertex, and the complement of an independent set is a vertex cover.
- Chromatic number facts: χ(Kn) = n, χ(even cycle) = 2, χ(odd cycle) = 3, and χ(G) is at least the size of the largest clique.
- Every connected graph has a spanning tree, which can be found by deleting cycle edges one at a time until no cycle remains.
- Kruskal's algorithm adds the cheapest edges that form no cycle; Prim's algorithm grows one tree by always adding the cheapest edge leaving it.
- A BFS spanning tree gives shortest root-to-vertex paths, while a DFS spanning tree goes deep and its non-tree edges always join ancestor and descendant.
Learn these by heart
- Euler's formula for a connected planar graph: v − e + f = 2
- Simple planar graph with v ≥ 3: e ≤ 3v − 6; if it has no triangles: e ≤ 2v − 4
- Handshaking lemma: Σ deg(v) = 2e
- A tree with n vertices has n − 1 edges; Cayley's formula: Kn has n^(n−2) spanning trees
- G is bipartite ⇔ G has no odd cycle ⇔ χ(G) = 2 (when G has at least one edge)
- χ(Kn) = n, χ(C2k) = 2, χ(C2k+1) = 3, and χ(planar graph) ≤ 4
2-mark questions
1 Define a multigraph and state how it differs from a simple graph. 2 marks
A multigraph is a graph in which a pair of vertices may be joined by more than one edge. These are called parallel or multiple edges. A simple graph allows at most one edge between two vertices and no loops. If loops are also allowed, the structure is usually called a pseudograph. The Königsberg bridge graph is an example of a multigraph.
2 What is a bipartite graph? Is the cycle C5 bipartite? 2 marks
A graph G is bipartite if its vertex set can be split into two disjoint sets V1 and V2 so that every edge joins a vertex of V1 to a vertex of V2. C5 is not bipartite. It is an odd cycle, so placing its vertices alternately in V1 and V2 forces two adjacent vertices into the same set.
3 A connected planar graph has 10 vertices and 15 edges. Find the number of regions in any plane drawing of it. 2 marks
By Euler's formula, v − e + f = 2.
So f = e − v + 2 = 15 − 10 + 2 = 7.
Every plane drawing of this graph has 7 regions (faces), and this count includes the one unbounded outer region.
4 Define the chromatic number of a graph. Write χ(Kn) and χ(C7). 2 marks
The chromatic number χ(G) is the least number of colours needed to colour the vertices of G so that no two adjacent vertices share a colour. χ(Kn) = n, because all n vertices are mutually adjacent. χ(C7) = 3, because an odd cycle cannot be 2-coloured but three colours are enough.
5 Define a vertex cover and an edge cover of a graph. 2 marks
A vertex cover is a set of vertices such that every edge has at least one end vertex in the set. An edge cover is a set of edges such that every vertex is an end of at least one edge in the set; it exists only when there are no isolated vertices. Covering problems look for the smallest such sets.
6 How many spanning trees does K4 have, and how many edges does each spanning tree contain? 2 marks
By Cayley's formula, Kn has n^(n−2) labelled spanning trees.
For K4: 4^(4−2) = 4^2 = 16 spanning trees.
Each spanning tree of a graph with 4 vertices has n − 1 = 4 − 1 = 3 edges.
10-mark questions
1 State and prove Euler's formula for connected planar graphs. Verify the formula for the complete graph K4 and the cube graph Q3. 10 marks
A graph is planar if it can be drawn in the plane so that edges meet only at their common end vertices. Such a drawing is called a plane graph. It divides the plane into connected regions called faces, and exactly one of these faces is unbounded.
Statement: If G is a connected planar graph with v vertices, e edges and f faces, then v − e + f = 2.
Proof (induction on the number of edges e):
1. Base case, e = 0. A connected graph with no edges is a single vertex. So v = 1 and f = 1, and 1 − 0 + 1 = 2.
2. Inductive hypothesis. Assume the formula holds for every connected plane graph with fewer than e edges, where e ≥ 1.
3. Case (a): G is a tree. A tree has e = v − 1 edges. Since it has no cycle, it does not enclose any region, so f = 1. Then v − (v − 1) + 1 = 2.
4. Case (b): G is not a tree, so G contains a cycle C. Choose an edge x on C. Because C is a closed curve, x separates a face inside C from a different face outside C.
5. Delete x. G − x is still connected, because the rest of C still joins the ends of x. G − x has v vertices and e − 1 edges. The two faces on either side of x merge into one, so it has f − 1 faces.
6. By the hypothesis, v − (e − 1) + (f − 1) = 2. This simplifies to v − e + f = 2.
The proof never uses simplicity of G. Loops and parallel edges also form cycles, so the formula holds for connected planar multigraphs too.
Verification for K4:
- v = 4 and e = 6.
- The faces are the three small inner triangles plus the outer region, so f = 4.
- 4 − 6 + 4 = 2. Verified.
Verification for Q3:
- v = 8 and e = 4 + 4 + 4 = 12.
- The faces are the inner square, the four four-sided regions between the squares, and the outer region, so f = 1 + 4 + 1 = 6.
- 8 − 12 + 6 = 2. Verified.
Conclusion: The number of faces of a connected planar graph is fixed by v and e (f = e − v + 2). It is therefore the same for every plane drawing. This formula is the starting point for the edge bounds used to prove that a graph is non-planar.
2 Prove that a connected simple planar graph with v ≥ 3 vertices and e edges satisfies e ≤ 3v − 6, and that if it has no triangles then e ≤ 2v − 4. Hence show that K5 and K3,3 are non-planar. 10 marks
These inequalities follow from Euler's formula v − e + f = 2. They give quick tests for non-planarity.
The degree of a face is the number of edge-sides on its boundary walk. Each edge either borders two faces or appears twice on the boundary of one face. So the sum of all face degrees is exactly 2e.
Part 1: e ≤ 3v − 6
1. G is simple, so there are no loops (faces of degree 1) and no parallel edges (faces of degree 2). Also v ≥ 3 means e ≥ 2. Even a tree's single face then has degree 2e ≥ 4. So every face has degree at least 3.
2. Therefore 2e = sum of face degrees ≥ 3f, which gives f ≤ 2e/3.
3. Substitute into Euler's formula: 2 = v − e + f ≤ v − e + 2e/3 = v − e/3.
4. So e/3 ≤ v − 2, that is, e ≤ 3v − 6.
Part 2: e ≤ 2v − 4 when there are no triangles
1. With no cycle of length 3 (and no loops or parallel edges), every face has degree at least 4.
2. So 2e ≥ 4f, which gives f ≤ e/2.
3. Then 2 = v − e + f ≤ v − e/2.
4. So e ≤ 2v − 4.
Application to K5:
- v = 5 and e = 5 × 4 / 2 = 10.
- 3v − 6 = 15 − 6 = 9.
- Since 10 > 9, the inequality e ≤ 3v − 6 fails, so K5 is not planar.
Application to K3,3:
- v = 6 and e = 3 × 3 = 9.
- The first test does not help, because 9 ≤ 3(6) − 6 = 12.
- K3,3 is bipartite, so all its cycles have even length and it has no triangles. The second inequality must therefore hold if it is planar.
- But 2v − 4 = 12 − 4 = 8, and 9 > 8.
- So K3,3 is not planar. This is the well-known three utilities problem.
Remarks:
- These conditions are necessary but not sufficient. A graph may satisfy e ≤ 3v − 6 and still be non-planar.
- Kuratowski's theorem gives an exact test: a graph is planar if and only if it contains no subdivision of K5 or K3,3.
- A further consequence of e ≤ 3v − 6 is that every simple planar graph has a vertex of degree at most 5.
Conclusion: Euler's formula, combined with the face-degree count 2e ≥ kf, gives simple edge bounds. These prove that K5 and K3,3, the two basic non-planar graphs, cannot be drawn without crossings.
3 Explain proper vertex colouring and the Welsh–Powell algorithm. Apply it to the graph G with vertices A, B, C, D, E, F and edges AB, AC, AD, AE, BC, CD, DE, EB, FB, FD. Find χ(G), and obtain a vertex cover of G from your colouring. 10 marks
A proper vertex colouring assigns colours to the vertices so that adjacent vertices always receive different colours. The chromatic number χ(G) is the least number of colours needed. All vertices with one colour form a colour class, which is an independent set: no two of its vertices are adjacent.
Welsh–Powell algorithm (greedy):
1. List the vertices in non-increasing order of degree. 2. Give the first uncoloured vertex in the list a new colour. 3. Move down the list. Give the same colour to every uncoloured vertex that is not adjacent to any vertex already holding that colour. 4. Repeat steps 2 and 3 until all vertices are coloured.
Step 1: Degrees
- A: B, C, D, E, so degree 4
- B: A, C, E, F, so degree 4
- D: A, C, E, F, so degree 4
- C: A, B, D, so degree 3
- E: A, B, D, so degree 3
- F: B, D, so degree 2
Check: 4 + 4 + 4 + 3 + 3 + 2 = 20 = 2 × 10 edges. The order is A, B, D, C, E, F.
Step 2: Colour 1. A gets colour 1. B, D, C and E are adjacent to A, so they are skipped. F is not adjacent to A, so F gets colour 1. Class 1 = {A, F}.
Step 3: Colour 2. B is the first uncoloured vertex and gets colour 2. D is not adjacent to B, so D gets colour 2. C and E are adjacent to B, so they are skipped. Class 2 = {B, D}.
Step 4: Colour 3. C gets colour 3. E is not adjacent to C, so E gets colour 3. Class 3 = {C, E}.
Verification of every edge (colours of the two ends):
- AB (1,2), AC (1,3), AD (1,2), AE (1,3), BC (2,3)
- CD (3,2), DE (2,3), EB (3,2), FB (1,2), FD (1,2)
The ends of every edge differ, so the colouring is proper and χ(G) ≤ 3.
Lower bound: A, B and C are mutually adjacent (edges AB, BC, AC), so they form a triangle. A triangle needs 3 colours, so χ(G) ≥ 3. Hence χ(G) = 3.
Vertex cover from the colouring: the complement of an independent set is always a vertex cover. If some edge had no end in the complement, both its ends would lie in the independent set, which is impossible.
- Take the independent set {A, F}.
- Its complement {B, C, D, E} is a vertex cover.
- Every edge listed above has at least one end in {B, C, D, E}, because AF is not an edge.
Conclusion: Welsh–Powell is a heuristic. On some graphs it may use more than χ(G) colours, so a lower bound such as a triangle or clique must be checked. Here the algorithm gives 3 colours and the triangle ABC shows this is optimal, so χ(G) = 3.
4 Define a multigraph and a bipartite graph. Prove that a graph without loops is bipartite if and only if it has no cycle of odd length. Deduce that a graph with at least one edge has chromatic number 2 if and only if it is bipartite. 10 marks
A multigraph is a graph in which two vertices may be joined by several parallel edges. Allowing loops as well gives a pseudograph. The handshaking rule still holds: the sum of degrees is 2e, with a loop adding 2 to the degree of its vertex.
A graph is bipartite if its vertex set splits into disjoint sets V1 and V2 so that every edge joins V1 to V2. A loop prevents this, since both its ends are the same vertex. Parallel edges cause no difficulty: two parallel edges form a cycle of length 2, which is even.
Theorem: A loopless graph G is bipartite if and only if G contains no odd cycle.
Proof of (⇒):
1. Let v0 v1 … v(k−1) v0 be a cycle of length k, and assume v0 ∈ V1. 2. Each edge changes sides, so vi ∈ V1 exactly when i is even. 3. The closing edge v(k−1)v0 must also change sides, so v(k−1) ∈ V2. Hence k − 1 is odd and k is even. 4. So every cycle has even length.
Proof of (⇐):
1. It is enough to bipartition each connected component, so assume G is connected. 2. Fix a vertex r. For each vertex x, let d(x) be the length of a shortest r–x path. 3. Put V1 = {x : d(x) even} and V2 = {x : d(x) odd}. 4. Suppose some edge xy has both ends in the same set, so d(x) and d(y) have the same parity. 5. Take a shortest r–x path P and a shortest r–y path Q. The closed walk formed by P, then edge xy, then Q reversed has length d(x) + 1 + d(y). This is odd. 6. Any closed walk of odd length contains an odd cycle. If a vertex repeats, split the walk there into two shorter closed walks; one of them must be odd. Repeat until no vertex repeats. 7. This contradicts the assumption that G has no odd cycle. So every edge joins V1 to V2, and G is bipartite.
Deduction about chromatic number:
- Suppose G is bipartite and has an edge. Colour V1 red and V2 blue; this is proper, so χ ≤ 2. An edge needs two different colours, so χ = 2.
- Conversely, suppose χ(G) = 2. The two colour classes are independent sets that partition V, so they form a bipartition.
- Therefore χ(G) = 2 if and only if G is bipartite (with at least one edge). Equivalently, any odd cycle forces χ(G) ≥ 3.
Examples:
- C6 and every Km,n are bipartite, so χ = 2.
- C5 contains an odd cycle, so χ(C5) = 3.
Conclusion: Bipartiteness, the absence of odd cycles and 2-colourability are three equivalent descriptions of the same property. The distance-parity proof also gives a practical test: run BFS and check that no edge joins two vertices at levels of the same parity.
5 Explain Kruskal's and Prim's algorithms for a minimum spanning tree. Using both, find a minimum spanning tree of the weighted graph with vertices A, B, C, D, E, F and edges AB = 4, AC = 3, BC = 2, BD = 5, CD = 7, CE = 8, DE = 6, DF = 4, EF = 5. 10 marks
A spanning tree of a connected graph with n vertices is a subgraph that is a tree and contains all n vertices; it has n − 1 edges. A minimum spanning tree (MST) is a spanning tree with the least total weight. Kruskal's and Prim's algorithms are both greedy methods for finding one.
Kruskal's algorithm:
1. Sort all edges in non-decreasing order of weight. 2. Take the edges in that order. Accept an edge if it does not form a cycle with the edges already accepted; otherwise reject it. 3. Stop when n − 1 edges have been accepted.
Prim's algorithm:
1. Start the tree from any single vertex. 2. At each step, add the cheapest edge that joins a tree vertex to a vertex not yet in the tree. 3. Stop when all n vertices are in the tree.
Kruskal's algorithm on the given graph:
Sorted edges: BC 2, AC 3, AB 4, DF 4, BD 5, EF 5, DE 6, CD 7, CE 8.
- BC (2): accept. Components {B, C}
- AC (3): accept. Components {A, B, C}
- AB (4): reject, because A and B are already connected (cycle A-B-C)
- DF (4): accept. Components {A, B, C}, {D, F}
- BD (5): accept. Components {A, B, C, D, F}
- EF (5): accept. Components {A, B, C, D, E, F}
Five edges have been accepted (n − 1 = 5), so the algorithm stops.
MST edges: BC, AC, DF, BD, EF.
Total weight = 2 + 3 + 4 + 5 + 5 = 19.
Prim's algorithm, starting at A:
- Tree {A}. Candidates AB 4, AC 3. Choose AC (3).
- Tree {A, C}. Candidates AB 4, CB 2, CD 7, CE 8. Choose CB (2).
- Tree {A, B, C}. Candidates BD 5, CD 7, CE 8 (AB now forms a cycle). Choose BD (5).
- Tree {A, B, C, D}. Candidates DF 4, DE 6, CE 8. Choose DF (4).
- Tree {A, B, C, D, F}. Candidates EF 5, DE 6, CE 8. Choose EF (5).
All six vertices are now in the tree.
Prim's tree: AC, CB, BD, DF, EF. Total weight = 3 + 2 + 5 + 4 + 5 = 19.
Comparison:
- Kruskal grows a forest that merges into one tree. It suits sparse graphs and runs in O(E log E) time because of the sorting.
- Prim always grows a single connected tree. It suits dense graphs and runs in O(V^2) with a simple array, or O(E log V) with a heap.
- Both rely on the cut property: the lightest edge crossing any cut belongs to some MST.
Conclusion: Both algorithms give a minimum spanning tree of weight 19 with edges AC, BC, BD, DF, EF.
6 Explain how breadth-first search (BFS) and depth-first search (DFS) produce spanning trees. For the graph with vertices a, b, c, d, e, f, g and edges ab, ac, bd, be, cf, de, eg, fg, construct the BFS and DFS spanning trees rooted at a, taking neighbours in alphabetical order. 10 marks
Every connected graph has a spanning tree. BFS and DFS find one by visiting every vertex once from a chosen root. Each new vertex is added to the tree using the edge through which it was first discovered. A graph with 7 vertices gets a spanning tree with 6 edges, so 2 of the 8 edges here will be left out.
Adjacency lists (alphabetical):
- a: b, c
- b: a, d, e
- c: a, f
- d: b, e
- e: b, d, g
- f: c, g
- g: e, f
BFS procedure:
mark root visited; enqueue root
while queue not empty:
u = dequeue
for each neighbour w of u (in order):
if w not visited: mark w; add edge uw to tree; enqueue wBFS from a:
1. Dequeue a. Discover b and c. Tree edges ab, ac. Queue: b, c. 2. Dequeue b. Discover d and e. Tree edges bd, be. Queue: c, d, e. 3. Dequeue c. Discover f. Tree edge cf. Queue: d, e, f. 4. Dequeue d. Its neighbours b and e are already visited. 5. Dequeue e. Discover g. Tree edge eg. Queue: f, g. 6. Dequeue f, then g. Nothing new is discovered.
BFS tree edges: ab, ac, bd, be, cf, eg (6 edges).
Levels: a at level 0; b, c at level 1; d, e, f at level 2; g at level 3.
Non-tree edges: de and fg. Each joins vertices whose levels differ by at most 1, which is always true in a BFS tree.
DFS procedure: from the current vertex, move to the first unvisited neighbour, adding that edge to the tree. If no unvisited neighbour remains, backtrack to the previous vertex.
DFS from a:
1. a → b (first unvisited neighbour of a). Tree edge ab. 2. b → d. Tree edge bd. 3. d → e. Tree edge de. 4. e → g (b and d are already visited). Tree edge eg. 5. g → f. Tree edge gf. 6. f → c. Tree edge fc. 7. c has no unvisited neighbour. Backtrack through f, g, e, d, b to a and stop.
DFS tree edges: ab, bd, de, eg, gf, fc (6 edges). Described in words, it is the single path a–b–d–e–g–f–c.
Non-tree edges: ac and be. Each joins a vertex to one of its ancestors, which is always true in a DFS tree.
Comparison:
- The BFS tree is short and bushy. Its tree path from the root to any vertex is a shortest path, so it is used for shortest paths in unweighted graphs and for testing bipartiteness.
- The DFS tree is long and deep. It is used for cycle detection, finding cut vertices and topological sorting.
- Both run in O(V + E) time.
Conclusion: For the given graph, BFS produces the tree {ab, ac, bd, be, cf, eg} and DFS produces the path tree {ab, bd, de, eg, gf, fc}. Both are valid spanning trees with 6 edges.
Public sources that settled doubtful points
Only the points the second AI pass doubted were looked up. These are the pages that confirmed or contradicted them; nothing here is copied from them.
Further reading
Titles only, for your own study. Nothing on this page is copied from them. The units follow the official JNTUK R23 CSE syllabus (PDF) ↗.
- Discrete Mathematical Structures with Applications to Computer Science · J. P. Tremblay and P. Manohar
- Elements of Discrete Mathematics: A Computer Oriented Approach · C. L. Liu and D. P. Mohapatra
- Theory and Problems of Discrete Mathematics (Schaum's Outline Series) · Seymour Lipschutz and Marc Lars Lipson
- Discrete Mathematics for Computer Scientists and Mathematicians · J. L. Mott, A. Kandel and T. P. Baker
- Discrete Mathematical Structures · Bernard Kolman, Robert C. Busby and Sharon Cutler Ross
- Discrete Mathematics · S. K. Chakraborty and B. K. Sarkar
- Discrete Mathematics and its Applications with Combinatorics and Graph Theory · K. H. Rosen