Rules of Inference and Proof Techniques

Part 1: Four Rules of Inference

Part 2: Proof of the Statement

Theorem: For any real number x, if x³ - 7x² + x - 7 = 0, then x = 7.

Note: The converse of this statement is NOT true in general (x = 7 gives 343 - 343 + 7 - 7 = 0 ✓, but x = i and x = -i also satisfy the equation). The correct interpretation for this exam is to prove: if x is a real number satisfying x³ - 7x² + x - 7 = 0, then x = 7 (since the other roots i and -i are not real).

Let:

• p: x³ - 7x² + x - 7 = 0
• q: x = 7

Method 1: Direct Proof (Proving p → q)

Assume p is true, i.e., assume:

$$x^3 - 7x^2 + x - 7 = 0$$

Step 1: Factor the left-hand side by grouping:

$$x^3 - 7x^2 + x - 7 = 0$$

$$x^2(x - 7) + 1(x - 7) = 0$$

Step 2: Factor out the common term (x - 7):

$$(x^2 + 1)(x - 7) = 0$$

Step 3: Apply the Zero Product Property. Either:

$$x^2 + 1 = 0 \quad \text{or} \quad x - 7 = 0$$

Step 4: Analyze each case:

• From x² + 1 = 0: x² = -1, which has no real solution (since x² ≥ 0 for all real x).
• From x - 7 = 0: x = 7 ✓

Step 5: Since x is a real number, the only valid solution is x = 7.

Therefore, if x³ - 7x² + x - 7 = 0, then x = 7. [Direct Proof Complete] ∎

Method 2: Indirect Proof (Proof by Contradiction, Proving p → q)

In indirect proof, we assume p is true and q is false, and derive a contradiction.

Assume:

• p is true: x³ - 7x² + x - 7 = 0
• q is false: x ≠ 7 (i.e., x is a real number and x ≠ 7)

Step 1: Factor the equation as before:

$$x^3 - 7x^2 + x - 7 = 0$$

$$x^2(x - 7) + 1(x - 7) = 0$$

$$(x^2 + 1)(x - 7) = 0$$

Step 2: Since we assumed x ≠ 7, we have (x - 7) ≠ 0.

Therefore, for the product to equal zero, we must have:

$$x^2 + 1 = 0$$

$$x^2 = -1$$

Step 3: But x is a real number, so x² ≥ 0 for all real x.

This means x² = -1 is impossible for any real number x.

Step 4: This is a contradiction -- we assumed x is real but arrived at x² = -1, which has no real solution.

Step 5: Therefore, our assumption that x ≠ 7 must be false.

Hence, x = 7 must be true.

[Indirect Proof Complete] ∎

Summary

Both methods confirm: For any real number x, if x³ - 7x² + x - 7 = 0, then x = 7.

Euler Path/Circuit Conditions and Partial Ordering Relation

Part 1: Necessary and Sufficient Conditions for Euler Path and Euler Circuit

Definitions

• Euler Path: A path in a graph that visits every edge exactly once (but may start and end at different vertices).
• Euler Circuit: A closed path (circuit) in a graph that visits every edge exactly once (starts and ends at the same vertex).

Conditions for Euler Circuit

Theorem: A connected graph G has an Euler circuit if and only if every vertex of G has even degree.

Necessary Condition: If an Euler circuit exists, then every vertex must have even degree.

• Reason: Every time the circuit enters a vertex, it must also leave it. So edges at each vertex are used in pairs, giving even degree.

Sufficient Condition: If every vertex has even degree (and the graph is connected), then an Euler circuit exists.

Conditions for Euler Path Only (Not a Circuit)

Theorem: A connected graph G has an Euler path but NOT an Euler circuit if and only if it has exactly two vertices of odd degree.

Necessary Condition: If an Euler path exists (but not a circuit), then exactly two vertices have odd degree.

• Reason: The path starts at one vertex and ends at another. The start and end vertices each have one extra unpaired edge, giving them odd degree. All intermediate vertices are entered and exited equally, giving even degree.

Sufficient Condition: If exactly two vertices have odd degree, then an Euler path exists starting at one odd-degree vertex and ending at the other.

Summary Table

Part 2: R is a Partial Ordering Relation on N

Given

Let R be a relation on N (natural numbers) such that:

$$aRb \iff ab = 2^k, \quad \text{where } k \in {0, 1, 2, \ldots}$$

This means: a divides b times a equals a power of 2, i.e., the product ab must be a power of 2.

Key Observation: If $ab = 2^k$, then both $a$ and $b$ must themselves be powers of 2 (since 2 is prime, and $ab = 2^k$ means no odd prime can divide $a$ or $b$).

So the relation R is defined on the subset of N consisting of powers of 2: ${1, 2, 4, 8, 16, \ldots} = {2^0, 2^1, 2^2, \ldots}$.

For $a = 2^i$ and $b = 2^j$, we have $ab = 2^{i+j} = 2^k$, so $k = i + j$.

Thus: $aRb \iff a = 2^i,\ b = 2^j$ for some $i, j \geq 0$.

This means $aRb$ holds whenever both $a$ and $b$ are powers of 2.

To Show: R is a Partial Order

A relation is a partial ordering if it is:

1. Reflexive
2. Antisymmetric
3. Transitive

1. Reflexivity: $aRa$ for all $a \in N$

We need $a \cdot a = a^2 = 2^k$ for some $k \geq 0$.

• For $a = 2^i$: $a \cdot a = 2^i \cdot 2^i = 2^{2i}$, which is a power of 2. So $aRa$ holds.
• For any $a$ that is a power of 2, reflexivity holds.

Therefore R is reflexive. $\checkmark$

2. Antisymmetry: If $aRb$ and $bRa$, then $a = b$

Suppose $aRb$ and $bRa$.

• $aRb \implies ab = 2^k$ for some $k \geq 0$
• $bRa \implies ba = 2^m$ for some $m \geq 0$

Since $ab = ba$, we have $2^k = 2^m$, so $k = m$.

Now, let $a = 2^i$ and $b = 2^j$.

• From $aRb$: $2^i \cdot 2^j = 2^{i+j} = 2^k$
• From $bRa$: $2^j \cdot 2^i = 2^{i+j} = 2^k$

Both give the same equation. For antisymmetry, we need to check if $aRb$ and $bRa$ forces $a = b$.

Since $ab = 2^k$ means $a$ and $b$ are both powers of 2, let $a = 2^i$, $b = 2^j$:

$$aRb: i + j = k \quad \text{and} \quad bRa: j + i = k$$

These are the same condition and do not force $i = j$ by themselves.

Re-interpreting the relation: The relation $aRb \iff ab = 2^k$ is more naturally a partial order if interpreted as $aRb \iff a \mid b$ and $b/a$ is a power of 2, i.e., $a \leq b$ in the divisibility order on powers of 2.

Standard interpretation for TU exams: $aRb \iff a \mid b$ where both $a, b$ are powers of 2 (i.e., $b = 2^k \cdot a$ for some $k \geq 0$). Under this reading:

• $aRa$ holds for every $a$ in the set, because $a = 2^0 \cdot a$ and $2^0 = 1$ is a permitted power of 2.
• $aRb$ together with $bRa$ gives $b = 2^k a$ and $a = 2^m b$, so $a = 2^{k+m} a$ and hence $2^{k+m} = 1$. Since $k, m \geq 0$ this forces $k = m = 0$, that is $a = b$.
• $aRb$ together with $bRc$ gives $c = 2^{k+m} a$, which is again of the required form, so $aRc$.

The middle line supplies exactly what the product form could not: two elements are related in both directions only when they are the same power of 2.

Therefore R is antisymmetric. $\checkmark$

3. Transitivity: If $aRb$ and $bRc$, then $aRc$

Suppose $aRb$ and $bRc$. Write $b = 2^k \cdot a$ and $c = 2^m \cdot b$ with $k, m \geq 0$. Substituting the first into the second,

$$c = 2^m \cdot (2^k \cdot a) = 2^{m+k} \cdot a$$

and since $m + k \geq 0$ the multiplier $2^{m+k}$ is itself a power of 2, so $aRc$ holds. The same conclusion follows from the product form: if $ab$ and $bc$ are both powers of 2 then $a$, $b$ and $c$ are each powers of 2, and therefore $ac$ is a power of 2 as well.

Therefore R is transitive. $\checkmark$

Conclusion

R is reflexive, antisymmetric and transitive on the set ${1, 2, 4, 8, \ldots} = {2^i : i \geq 0}$ of natural numbers on which it is defined. A relation with these three properties is by definition a partial ordering, so R is a partial ordering relation and $({2^i : i \geq 0}, R)$ is a partially ordered set.

Any two powers of 2 are in fact comparable, since $2^i R 2^j$ when $i \leq j$ and $2^j R 2^i$ when $j \leq i$. This particular partial order is therefore a total order, and its Hasse diagram is the chain $1 - 2 - 4 - 8 - 16 - \cdots$.

GCD of 12 and 16 using the Extended Euclidean Algorithm

Step 1 - Given Data

• $a = 16$, $b = 12$ (arranged so larger is first)
• Goal: find $\gcd(12,16)$ and integers $s, t$ such that $\gcd = s\cdot 12 + t\cdot 16$

Step 2 - Apply the Euclidean Algorithm (Successive Division)

The last non-zero remainder is $4$.

$$\gcd(12, 16) = 4$$

Step 3 - Back-Substitution (Express as Linear Combination)

From Step 1, isolate the remainder $4$:

$$4 = 16 - 1 \times 12$$

Rewrite explicitly as a linear combination of $12$ and $16$:

$$4 = (-1)\times 12 + (1)\times 16$$

So the coefficients are:

$$s = -1, \qquad t = 1$$

Step 4 - Verification

$$s\cdot 12 + t\cdot 16 = (-1)(12) + (1)(16) = -12 + 16 = 4 \ \checkmark$$

Result

$$\boxed{\gcd(12, 16) = 4 = (-1)\cdot 12 + (1)\cdot 16}$$

Chromatic Number and Kruskal's Algorithm

Part 1: Chromatic Number (Definition)

The chromatic number of a graph G is the minimum number of colors required to color the vertices of G such that no two adjacent vertices (vertices connected by an edge) share the same color.

It is denoted by χ(G) (chi of G).

Examples:

• A complete graph K_n has chromatic number χ(K_n) = n
• A cycle with an even number of vertices has χ = 2
• A cycle with an odd number of vertices has χ = 3
• A tree (with more than one vertex) has χ = 2

Part 2: Kruskal's Algorithm for Minimum Spanning Tree

A Minimum Spanning Tree (MST) of a weighted graph G is a spanning tree whose total edge weight is minimum among all possible spanning trees.

Steps of Kruskal's Algorithm

Step 1: List all the edges of G in non-decreasing order of their weights.

Step 2: Select the edge of minimum weight. This becomes the first edge of the spanning tree T. (If two edges have equal minimum weight, choose arbitrarily.)

Step 3: At each subsequent stage, select the edge of minimum weight from the remaining edges of G, provided it does not form a cycle with the previously selected edges in T. Add this edge to T.

Step 4: Repeat Step 3 until n - 1 edges have been selected (where n is the number of vertices).

The resulting tree T is the Minimum Spanning Tree.

Illustrative Example

Consider a weighted graph with vertices {A, B, C, D} and edges:

Step 1: Sort edges by weight: A-B (1), B-D (2), B-C (3), A-C (4), C-D (5)

Step 2: Select A-B (weight 1). T = {A-B}

Step 3:

• Select B-D (weight 2). No cycle formed. T = {A-B, B-D}
• Select B-C (weight 3). No cycle formed. T = {A-B, B-D, B-C}
• We now have n - 1 = 3 edges. Stop.

MST Total Weight = 1 + 2 + 3 = 6

Key Property

Kruskal's algorithm is a greedy algorithm that always picks the globally minimum weight edge that does not create a cycle, guaranteeing an optimal (minimum weight) spanning tree.

Solving the Recurrence Relation $a_n = a_{n-1} + 2a_{n-2}$

Given Data

• Recurrence: $a_n = a_{n-1} + 2a_{n-2}$
• Initial conditions: $a_0 = 2$, $a_1 = 7$

Step 1: Characteristic Equation

This is a linear homogeneous recurrence with constant coefficients. Assume $a_n = r^n$:

$$r^n = r^{n-1} + 2r^{n-2}$$

Divide by $r^{n-2}$:

$$r^2 = r + 2 \implies r^2 - r - 2 = 0$$

Step 2: Solve for Roots

$$r^2 - r - 2 = (r-2)(r+1) = 0$$

$$r_1 = 2, \quad r_2 = -1$$

Distinct roots, so the general solution is:

$$a_n = \alpha_1 (2)^n + \alpha_2 (-1)^n$$

Step 3: Apply Initial Conditions

From $a_0 = 2$: $$\alpha_1 + \alpha_2 = 2 \quad (i)$$

From $a_1 = 7$: $$2\alpha_1 - \alpha_2 = 7 \quad (ii)$$

Adding $(i)$ and $(ii)$: $$3\alpha_1 = 9 \implies \alpha_1 = 3$$

From $(i)$: $$\alpha_2 = 2 - 3 = -1$$

Step 4: Final Solution

$$\boxed{a_n = 3 \cdot 2^n - (-1)^n}$$

Verification

The solution is confirmed correct.

Network Flow

Definition

A network flow (or transport network) is a directed graph G = (V, E) where each edge e has an associated capacity C(e) > 0, a designated source node S (only outgoing flow) and a sink/destination node D (only incoming flow). All other vertices are called intermediate vertices.

The network flow problem asks: what is the maximum total amount of flow that can be carried from source S to destination D?

Key Constraints:

• The flow on any edge cannot exceed its capacity: F(e) ≤ C(e)
• For every intermediate vertex, flow in = flow out (conservation of flow)

Important Terminology

Consider an edge with notation C(e), F(e) meaning capacity C(e) and current flow F(e):

Examples

Consider the following edges in a transport network (written as capacity, flow):

Example Edge Set:

Edge (S, a):  capacity = 10,  flow = 10
Edge (a, b):  capacity = 8,   flow = 5
Edge (b, D):  capacity = 6,   flow = 3

1. Saturated Edge

Edge (S, a): C = 10, F = 10

Since F(e) = C(e) = 10, this edge is saturated. No additional flow can be pushed through this edge.

Slack = 10 - 10 = 0

2. Unsaturated Edge

Edge (a, b): C = 8, F = 5

Since F(e) = 5 < C(e) = 8, this edge is unsaturated. This edge can still carry additional flow and can be part of an augmenting path.

Slack = 8 - 5 = 3

3. Slack

Edge (b, D): C = 6, F = 3

Slack = C(e) - F(e) = 6 - 3 = 3

This means 3 more units of flow can still be pushed through edge (b, D).

Significance in Maximum Flow

• An augmenting path from S to D is a simple path consisting entirely of unsaturated (forward) edges.
• Once all paths from S to D contain at least one saturated edge, no more augmenting paths exist and the maximum flow has been achieved.
• The maximum flow equals the sum of outgoing flows at S = sum of incoming flows at D.

Subset, Power Set, and Proving Correctness of Recursive Algorithms by Induction

1. Subset

A set A is called a subset of set B if every element of A is also an element of B. This is denoted as:

A ⊆ B if and only if ∀x (x ∈ A → x ∈ B)

Example: If A = {a, b} and B = {a, b, c}, then A ⊆ B.

• The empty set (∅) is a subset of every set.
• Every set is a subset of itself.

2. Power Set

The power set of a set S is the set of all subsets of S, including the empty set. It is denoted as P(S).

If |S| = n, then |P(S)| = 2ⁿ

Example (from notes): For S = {a, b, c, d}, the power set P(S) contains:

Total subsets = 1 + 4 + 6 + 4 + 1 = 16 = 2⁴ ✓

3. Proving Correctness of a Recursive Algorithm Using Induction

Mathematical induction is the standard method for proving that a recursive algorithm produces the correct result for all valid inputs.

Steps:

1. Base Case: Show the algorithm gives the correct output for the smallest/simplest input.
2. Inductive Hypothesis: Assume the algorithm works correctly for all inputs of size less than n (or for input n = k).
3. Inductive Step: Show that if the algorithm works for smaller inputs (by the hypothesis), it also works correctly for input of size n (or n = k+1).

4. Illustration: Recursive Factorial Algorithm

Algorithm:

factorial(n):
    if n = 0 then
        return 1
    else
        return n * factorial(n - 1)

Claim: factorial(n) correctly computes n! for all n ≥ 0.

Proof by Mathematical Induction:

Base Case (n = 0):

The algorithm returns 1 when n = 0. By definition, 0! = 1. Therefore, the algorithm is correct for n = 0. ✓

Inductive Hypothesis:

Assume factorial(k) correctly computes k! for some arbitrary k ≥ 0. That is, assume factorial(k) returns k!.

Inductive Step (show it works for n = k + 1):

When the algorithm is called with input (k + 1):

• Since k + 1 > 0, it executes: return (k+1) * factorial(k)
• By the inductive hypothesis, factorial(k) returns k!
• Therefore, the algorithm returns:

$$ (k+1) \times k! = (k+1)! $$

This is exactly the correct value of (k+1)!. ✓

Conclusion:

By the principle of mathematical induction, factorial(n) correctly computes n! for all n ≥ 0.

This demonstrates that induction mirrors the recursive structure of the algorithm: the base case handles the termination condition, and the inductive step handles the recursive call.