Make learning comfortable
Discrete Mathematics / LEVEL 1 · DIFFICULTY 4/5
Discrete Mathematics
Read the prerequisite, study a worked example and justify each step in these selected university topics.
Choose a node to explore its lesson.
STAGE UDIS 1.1 · 8 PRACTICE PROBLEMS · 4 NEW-CONTEXT APPLICATIONS
Logic, Sets & Relations
Useful preparation: Product Rule
Open this topic in the university library →
For a long equation, swipe sideways inside its formula box to see every term.
Meaning & notation
“Every input has a suitable output” permits different outputs for different inputs; “one output works for every input” does not. Logic makes this distinction precise.
- Predicate and quantifier
- A predicate P(x) becomes a statement when its variable is specified or quantified. The symbols ∀ and ∃ mean “for every” and “there exists”; the domain determines the allowed choices.
- Sets and membership
- A union contains elements in either set, an intersection contains elements in both, and A⊆B means every member of A belongs to B.
- Relation and equivalence class
- A relation R on A is a subset of . Write xRy for membership of the pair. An equivalence class [x] collects all elements related to x.
Conditions before calculation
- State every variable’s domain and preserve the order of nested quantifiers. A later existential choice may depend on earlier universally chosen variables.
- An equivalence relation must be reflexive, symmetric, and transitive on the entire declared set.
- A partial order instead requires reflexivity, antisymmetry, and transitivity. Antisymmetry permits mutual relatedness only for equal elements.
Why the method works
1. Negate from outside inward
To refute a universal assertion, supply one failing input. To refute an existential assertion, rule out every allowed witness. Repeating these rules handles nested statements.
2. Translate implication accurately
The implication rules out a true premise with a false conclusion. Its contrapositive describes exactly the same forbidden situation; its converse generally describes something else.
3. Explain why classes partition
Reflexivity places each element in its own class. If two classes overlap, symmetry and transitivity transfer membership between them, so they coincide rather than overlap partially.
Worked examples
EXAMPLE 1
Compare “for every integer n, some integer m exceeds n” with the reversed quantifier order.
Choose an arbitrary integer n. The expression is an allowed integer witness.
This witness exceeds n, proving the first statement without selecting a special input.
For the reversed claim, any proposed fixed m fails at . Thus no single witness works for all integers.
Conclusion: The first claim is true; the reversed claim is false.
EXAMPLE 2
On the integers, define aRb when 5 divides . Verify equivalence and identify [2].
The difference is zero, a multiple of 5, so reflexivity holds.
Negating a multiple of 5 gives another multiple, proving symmetry.
If and , add them; is an integer.
All and only integers differing from 2 by a multiple of 5 belong to its class.
Conclusion: The relation partitions the integers into five remainder classes.
Pitfalls & counterexamples
Tempting claim: Symmetric and antisymmetric mean the same thing.
Correction: Symmetry requires the reverse pair; antisymmetry restricts when both directions can occur.
Test the claim: The relation ≤ on integers is antisymmetric, but does not imply .
Check your understanding
Negate: for every real x, there exists a real y with .
Write a reason before opening the explanation. This reflection is not graded or saved.
Compare your reasoning
There exists a real x such that every real y satisfies .
Switch both quantifiers and negate the strict inequality. Keep their order.
Connect this idea
Equivalence classes lead to modular arithmetic and quotient structures. Quantifier order also distinguishes pointwise convergence from uniform convergence.
Reference reading
Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.
Preview the eight practice prompts
For the implication “if n is divisible by 4, then n is divisible by 2,” which equivalent form is the contrapositive? Enter 1 for “if not divisible by 2, then not divisible by 4”, or 2 for the converse.
Two finite sets have sizes 6 and 8, with intersection size 2. Find their union size.
On the integers a~b when is divisible by 3. How many equivalence classes are there?
Consider the claim “every integer n is less than 4.” Which negates it? Enter 1 for “some integer n is at least 4”, 2 for “every integer n is at least 4”.
A rule says “if n is divisible by 6, then n is divisible by 3,” which equivalent form is the contrapositive? Enter 1 for “if not divisible by 3, then not divisible by 6”, or 2 for the converse.
Two membership lists have sizes 7 and 9, with intersection size 3. Find their union size.
An integer classification uses a~b when is divisible by 4. How many equivalence classes are there?
A program specification claims “every integer n is less than 5.” Which negates it? Enter 1 for “some integer n is at least 5”, 2 for “every integer n is at least 5”.
STAGE UDIS 1.2 · 8 PRACTICE PROBLEMS · 4 NEW-CONTEXT APPLICATIONS
Graphs, Trees & Discrete Models
Useful preparation: Logic, Sets & Relations
Open this topic in the university library →
For a long equation, swipe sideways inside its formula box to see every term.
Meaning & notation
Graphs retain connections rather than physical distances. Counting edges and degrees can reveal impossible routes before drawing them.
- Finite simple undirected graph
- has finitely many vertices and unordered edges between distinct vertices, without loops or repeated edges. Degree counts the edges incident to a vertex.
- Path, cycle, and tree
- A path has no repeated vertices. A cycle returns to its initial vertex without other repetition. A tree is a connected graph with no cycles.
- Euler trail
- An Euler trail uses every edge exactly once and may revisit vertices. It is an Euler circuit when it ends where it starts; a Hamilton path instead visits every vertex once.
Conditions before calculation
- Tree edge counts here concern finite nonempty graphs. Having edges characterizes a tree only when connectivity is also known.
- For an undirected graph with at least one edge, all vertices of positive degree must lie in one connected component for an Euler trail to exist.
- Under that connectivity condition, zero odd-degree vertices permit a circuit; exactly two permit an open Euler trail. More than two prevent either.
Why the method works
1. Count every edge twice
Each undirected edge has two endpoints, so summing degrees counts it twice. Consequently the number of odd-degree vertices is even.
2. Understand tree rigidity
A tree has a unique path between two vertices: two different paths would create a cycle. Removing a leaf removes one vertex and one edge, reducing the edge formula to a smaller tree.
3. Pair arrivals with departures
At every internal visit of an Euler trail, one unused edge brings the route in and another takes it out. Only distinct starting and ending vertices can have unpaired incidences.
Worked examples
EXAMPLE 1
A graph has vertices A,B,C,D,E and edges AB, BC, CD, DA, AC, CE. Find an Euler trail.
Its degrees are 3,2,4,2,1 respectively. Their sum is 12, confirming that there are six edges.
All vertices are connected; A and E are the only odd-degree vertices, so an open trail must start and end there.
The route E,C,B,A,D,C,A uses EC, CB, BA, AD, DC, CA once each, verifying existence directly.
Conclusion: An Euler trail runs from E to A; no Euler circuit exists.
EXAMPLE 2
A tree has edges AB, AC, BD, BE, CF, CG. Add the new edge DE. Describe the resulting cycle.
The seven vertices are connected by six edges, and the branching structure has no cycle.
The original unique path from D to E is D,B,E. The added edge closes precisely that path.
Deleting DE restores a tree, so every cycle would have to use DE. Uniqueness of the original path leaves only D,B,E,D.
Conclusion: Exactly one cycle is created, with three edges.
Pitfalls & counterexamples
Tempting claim: Any graph with one fewer edge than vertices is a tree.
Correction: The count must be accompanied by connectivity.
Test the claim: A triangle plus an isolated vertex has four vertices and three edges, but is disconnected and contains a cycle.
Check your understanding
If edge AE is added to the first example, can the new graph have an Euler circuit?
Write a reason before opening the explanation. This reflection is not graded or saved.
Compare your reasoning
Yes.
A and E both become even-degree vertices. The graph remains connected and now all degrees are even.
Connect this idea
Degree sums use double counting. Tree arguments invite induction; connectivity converts local degree information into global route guarantees.
Reference reading
Use these texts to study the underlying definitions and theorems in greater depth. The explanations and examples above are written for Numerive.
Preview the eight practice prompts
A graph has total degree 14. How many edges does it have?
A tree has 9 vertices. How many edges does it have?
A connected graph has 8 vertices, exactly 4 of odd degree. Can a single trail use every edge once? Enter 1 for yes or 0 for no.
A tree has 6 vertices. One new edge is added between two previously nonadjacent vertices. How many independent cycles result?
A network has total degree 16. How many edges does it have?
A tree-shaped communication network has 10 vertices. How many edges does it have?
A connected route network has 9 vertices, exactly 4 of odd degree. Can a single trail use every edge once? Enter 1 for yes or 0 for no.
A connected tree network has 7 vertices. One new edge is added between two previously nonadjacent vertices. How many independent cycles result?