Euler Circuit and Maximum Network Flow

STEP 1 - EXTRACT: Given Data

Part 1 (Euler Circuit): Purely definitional; requires a self-constructed example. No numeric data supplied.

Part 2 (Maximum Flow):

• A network with source $s$ and sink $t$ is referenced.
• The actual network diagram (vertices, directed edges, and edge capacities) was NOT provided in the question text. Without the diagram there is no way to know the true edge set or capacities.

Missing data statement: The network flow diagram for Part 2 is missing. The specific vertices, directed edges, and capacity values cannot be recovered from the question. Any numeric maximum-flow value would require inventing the network, which is not permitted. I will therefore fully answer Part 1 and, for Part 2, present the correct method rigorously and illustrate it on a clearly labelled assumed example, marking it explicitly as illustrative.

STEP 2 - SOLVE

Part 1: Euler Circuit (Definition + Example)

Definition. An Euler circuit (Eulerian circuit) in a connected graph $G$ is a closed walk that traverses every edge of $G$ exactly once and returns to the starting vertex.

Existence Theorem (Euler). A connected graph $G$ has an Euler circuit if and only if every vertex has even degree. (A graph has an Euler path but not a circuit iff exactly two vertices have odd degree.)

Suitable Example.

Take a triangle graph $G$ with vertices ${A, B, C}$ and edges ${A\text{-}B,\ B\text{-}C,\ C\text{-}A}$.

        A
       / \
      /   \
     C-----B

Degrees: $$\deg(A)=2,\quad \deg(B)=2,\quad \deg(C)=2$$

All degrees are even and the graph is connected, so an Euler circuit exists.

Euler circuit: $A \to B \to C \to A$

This traverses each of the 3 edges exactly once and returns to $A$. Hence it is a valid Euler circuit.

Part 2: Maximum Flow $s \to t$ (Ford-Fulkerson Method)

Important: The actual network diagram was not reproduced in the question, so the numeric answer below is based on an assumed illustrative network. Replace the capacities with those in your exam diagram; the procedure is identical.

Algorithm (Ford-Fulkerson augmenting path):

1. Initialise flow $f = 0$ on every edge.
2. While an augmenting path $s \to t$ exists in the residual graph:
   • Find bottleneck $c_{\min}=\min$ residual capacity on the path.
   • Add $c_{\min}$ to forward edges, subtract from backward edges.
3. Maximum flow $=$ total flow leaving $s$ (verified by min-cut).

Assumed network capacities:

Iteration 1: Path $s\to a\to t$, bottleneck $=\min(5,6)=5$. $f(s,a)=5,\ f(a,t)=5$.

Iteration 2: Path $s\to b\to c\to t$, bottleneck $=\min(4,5,6)=4$. $f(s,b)=4,\ f(b,c)=4,\ f(c,t)=4$.

Iteration 3: Check residuals.

• $s\to a$: $5-5=0$ (saturated)
• $s\to b$: $4-4=0$ (saturated)

Both edges out of $s$ are saturated, so no augmenting path remains.

Maximum flow (for this assumed network): $$f_{\max}=f(s,a)+f(s,b)=5+4=\boxed{9}$$

Min-cut check: The cut ${s}\ /\ \text{rest}$ has capacity $c(s,a)+c(s,b)=5+4=9$, matching the flow, confirming optimality by the max-flow min-cut theorem.

Conclusion: For the assumed network, the maximum flow from $s$ to $t$ is 9 units. For the exam's actual diagram, apply the same augmenting-path steps to the given capacities.

Euler Path and Hamilton Path

Euler Path

Definition: An Euler path (also called an Eulerian trail) is a path in a graph that traverses every edge exactly once. The initial and terminal vertices of the path need not be the same. If the initial and terminal vertices are the same, it is called an Euler circuit.

Condition for Euler Path: A connected graph has an Eulerian trail if and only if it has exactly two vertices of odd degree. The path must start at one odd-degree vertex and end at the other.

Example of Euler Path:

Consider a graph with vertices: A, B, C, D and edges: A-B, A-C, B-C, B-D, C-D

A --- B
|   / |
| /   |
C --- D

Here deg(A) = 2, deg(B) = 3, deg(C) = 3 and deg(D) = 2, so exactly two vertices, B and C, have odd degree. An Euler path therefore exists, and it has to start at one odd vertex and finish at the other:

B → A → C → D → B → C

This walk uses the edges A-B, A-C, C-D, B-D and B-C, that is all five edges of the graph, each exactly once. Because two vertices have odd degree the walk cannot come back to where it started, so this graph has an Euler path but no Euler circuit.

Hamilton Path

Definition: A Hamiltonian path is a simple path that contains all vertices of a graph G exactly once. Unlike the Euler path, it focuses on visiting every vertex exactly once rather than every edge. If the path returns to the starting vertex, it is called a Hamiltonian cycle.

Note: There is no simple necessary and sufficient condition (like for Euler path) to determine the existence of a Hamiltonian path.

Example of Hamilton Path:

Consider a graph with vertices: 1, 2, 3, 4, 5 and edges connecting them as a cycle with some additional edges.

1 - 2 - 3 - 4 - 5

The path 1 → 2 → 3 → 4 → 5 visits every vertex exactly once. This is a Hamiltonian path.

Comparison Table

Key Difference

• Euler Path is concerned with covering every edge exactly once.
• Hamilton Path is concerned with visiting every vertex exactly once.

Floor and Ceiling Functions, and Inclusion-Exclusion Principle

1. Floor Function

The floor function for any real number x is defined as the greatest integer less than or equal to x.

It is denoted by ⌊x⌋.

Examples:

• ⌊3.5⌋ = 3
• ⌊-2.4⌋ = -3 (since -3 is the greatest integer less than or equal to -2.4)
• ⌊3.143⌋ = 3

2. Ceiling Function

The ceiling function for any real number x is defined as the smallest integer greater than or equal to x.

It is denoted by ⌈x⌉.

Examples:

• ⌈3.5⌉ = 4
• ⌈-2.4⌉ = -2 (since -2 is the smallest integer greater than or equal to -2.4)
• ⌈3.143⌉ = 4

3. Inclusion-Exclusion Principle

Why Do We Need It?

When counting elements in the union of two or more sets, simply adding the sizes of individual sets overcounts the elements that appear in more than one set. The Inclusion-Exclusion Principle corrects this overcounting by systematically including and excluding overlapping regions.

Without this principle, we would either overcount (by counting shared elements multiple times) or undercount (by ignoring them). It gives us an exact count of elements in the union of finite sets.

Statement

For any two finite sets A and B:

$$n(A \cup B) = n(A) + n(B) - n(A \cap B)$$

For three finite sets A, B, and C:

$$n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(A \cap C) - n(B \cap C) + n(A \cap B \cap C)$$

Here we include individual set sizes, exclude pairwise intersections, and include the triple intersection back.

Suitable Example

Problem: In a town of 10,000 families:

• 40% buy newspaper A → n(A) = 4000
• 20% buy newspaper B → n(B) = 2000
• 10% buy newspaper C → n(C) = 1000
• 5% buy A and B → n(A ∩ B) = 500
• 3% buy B and C → n(B ∩ C) = 300
• 4% buy A and C → n(A ∩ C) = 400
• 2% buy all three → n(A ∩ B ∩ C) = 200

Find: Number of families that buy at least one newspaper.

Solution using Inclusion-Exclusion:

$$n(A \cup B \cup C) = n(A) + n(B) + n(C) - n(A \cap B) - n(A \cap C) - n(B \cap C) + n(A \cap B \cap C)$$

$$= 4000 + 2000 + 1000 - 500 - 400 - 300 + 200$$

$$= 7000 - 1200 + 200 = \mathbf{6000}$$

Number of families buying none of the newspapers:

$$= 10000 - 6000 = \mathbf{4000}$$

Conclusion

The Inclusion-Exclusion Principle is essential in combinatorics and set theory to accurately count elements in unions of overlapping sets, avoiding both overcounting and undercounting of shared elements.