Graph Theory

Goal: Find and mathematically justify the vertex and edge counts for standard graph families.

Step-by-Step Derivation:

• (a) Complete Graph $K_n$:
  • Vertices: By definition, $K_n$ has $n$ vertices.
  • Edges: Every pair of vertices is connected by a unique edge. The number of ways to choose 2 vertices from $n$ is: $$|E| = \binom{n}{2} = \frac{n(n-1)}{2}$$
• (b) Cycle Graph $C_n$ ($n \geq 3$):
  • Vertices: By definition, $C_n$ has $n$ vertices.
  • Edges: The vertices are arranged in a closed loop, where $v_i$ connects to $v_{i+1}$ (and $v_n$ connects to $v_1$). This forms exactly $n$ edges.
• (c) Wheel Graph $W_n$ ($n \geq 3$):
  • Vertices: Consists of a cycle $C_n$ of $n$ rim vertices plus a single central hub vertex. Thus, $|V| = n + 1$.
  • Edges: Consists of the $n$ edges forming the rim cycle, plus $n$ "spoke" edges connecting the hub to each of the $n$ rim vertices. Thus, $|E| = 2n$.
• (d) Complete Bipartite Graph $K_{m,n}$:
  • Vertices: The vertex set is partitioned into two disjoint subsets of sizes $m$ and $n$. Thus, $|V| = m + n$.
  • Edges: Every vertex in the first partition connects to every vertex in the second partition. This yields $|E| = m \cdot n$.
• (e) Hypercube Graph $Q_n$:
  • Vertices: Vertices are represented by binary strings of length $n$. Since there are $2$ options ($0$ or $1$) for each of the $n$ bits, $|V| = 2^n$.
  • Edges: Two vertices are adjacent if their binary strings differ in exactly $1$ bit. Thus, each vertex has exactly $n$ neighbors (making the graph $n$-regular). By the Handshaking Lemma: $$2|E| = \sum_{v \in V} \deg(v) = n \cdot |V| = n \cdot 2^n \implies |E| = n \cdot 2^{n-1}$$

∎

Goal: Determine the bipartiteness condition for each graph family using the characterization that a graph is bipartite if and only if it contains no odd-length cycles.

Step-by-Step Analysis:

• (a) Complete Graph $K_n$: If $n \geq 3$, $K_n$ contains a triangle ($C_3$, which is an odd cycle). Thus, it cannot be bipartite. For $n=1$ (no edges) and $n=2$ (a single edge, no cycles), the graph contains no odd cycles. Condition: Bipartite iff $n \leq 2$.
• (b) Cycle Graph $C_n$: $C_n$ contains a single cycle of length $n$. If $n$ is odd, it is an odd cycle, so it is not bipartite. If $n$ is even, it contains no odd cycles, so it is bipartite. Condition: Bipartite iff $n$ is even.
• (c) Wheel Graph $W_n$: For any wheel graph, any two adjacent vertices on the rim form a triangle ($C_3$) with the central hub vertex. Since $C_3$ is an odd cycle, $W_n$ always contains an odd cycle. Condition: Never bipartite for any $n \geq 3$.
• (d) Hypercube Graph $Q_n$: Let the vertices be represented by binary strings of length $n$. Partition the vertices into:
  • $V_1$: strings containing an even number of 1s
  • $V_2$: strings containing an odd number of 1s
  Since adjacent vertices in $Q_n$ differ in exactly one bit position, any edge must connect a vertex with an even number of 1s to a vertex with an odd number of 1s. No edges exist within $V_1$ or within $V_2$. Condition: Always bipartite for all $n \geq 1$.

∎

Goal: Calculate the degree sequence for each specified graph.

Step-by-Step Derivation:

• (a) $K_4$: Every vertex in a complete graph on $n$ vertices has degree $n-1$. $$\text{Degree sequence: } (3, 3, 3, 3)$$
• (b) $C_4$: Every vertex in a cycle has exactly 2 neighbors. $$\text{Degree sequence: } (2, 2, 2, 2)$$
• (c) $W_4$: Consists of a central hub (connected to all 4 rim vertices, degree 4) and 4 rim vertices (each connected to 2 rim neighbors and the hub, degree 3). $$\text{Degree sequence: } (4, 3, 3, 3, 3)$$
• (d) $K_{2,3}$: Bipartite graph. The 2 vertices in the first partition connect to 3 vertices $\implies$ degree 3. The 3 vertices in the second partition connect to 2 vertices $\implies$ degree 2. $$\text{Degree sequence: } (3, 3, 2, 2, 2)$$
• (e) $Q_3$: Every vertex in $Q_3$ is 3-regular because there are 3 bits to flip. $$\text{Degree sequence: } (3, 3, 3, 3, 3, 3, 3, 3)$$
• (f) $K_{m,n}$: Consists of $m$ vertices of degree $n$, and $n$ vertices of degree $m$. $$\text{Degree sequence: } (\underbrace{n, \dots, n}_{m \text{ times}}, \underbrace{m, \dots, m}_{n \text{ times}}) \quad \text{sorted in non-increasing order}$$
• (g) $K_n$: A complete graph of size $n$ has every vertex connected to all other $n-1$ vertices. $$\text{Degree sequence: } (n-1, n-1, \dots, n-1) \quad \text{of length } n$$

∎

Goal: Compute the edge count using the Handshaking Lemma and construct a simple graph for each degree sequence.

Step-by-Step Derivation:

• (a) Sequence: $4, 3, 3, 2, 2$:
  1. Calculate edge count $|E|$: By the Handshaking Lemma, $\sum \deg(v) = 2|E|$: $$4 + 3 + 3 + 2 + 2 = 14 \implies 2|E| = 14 \implies |E| = 7$$
  2. Construction: Let the vertices be $\{A, B, C, D, E\}$ with target degrees $4, 3, 3, 2, 2$. Since $A$ has degree 4, it must connect to all other 4 vertices: $$\text{Edges: } \{A, B\}, \{A, C\}, \{A, D\}, \{A, E\}$$ The remaining degrees required are $B: 2, C: 2, D: 1, E: 1$. Connect $B$ to $C$ (both now need 1 more edge) and $B$ to $D$ (D is fully satisfied). Connect $C$ to $E$ (both are now satisfied). $$\text{Additional Edges: } \{B, C\}, \{B, D\}, \{C, E\}$$ This gives a total of 7 edges. Verifying degrees: $\deg(A)=4, \deg(B)=3, \deg(C)=3, \deg(D)=2, \deg(E)=2$.
• (b) Sequence: $5, 2, 2, 2, 2, 1$:
  1. Calculate edge count $|E|$: $$5 + 2 + 2 + 2 + 2 + 1 = 14 \implies 2|E| = 14 \implies |E| = 7$$
  2. Construction: Let the vertices be $\{H, A, B, C, D, E\}$ with target degrees $5, 2, 2, 2, 2, 1$. Since $H$ has degree 5, it connects to all other 5 vertices: $$\text{Edges: } \{H, A\}, \{H, B\}, \{H, C\}, \{H, D\}, \{H, E\}$$ The remaining degrees required are $A: 1, B: 1, C: 1, D: 1, E: 0$. Vertex $E$ is already satisfied (degree 1). We add 2 more edges to satisfy the remaining vertices: connect $A$ to $B$, and $C$ to $D$. $$\text{Additional Edges: } \{A, B\}, \{C, D\}$$ Verifying degrees: $\deg(H)=5, \deg(A)=2, \deg(B)=2, \deg(C)=2, \deg(D)=2, \deg(E)=1$.

∎

Goal: Formally prove that the average degree $\frac{2e}{v}$ is bounded by the minimum and maximum degrees of the graph.

Proof:

1. Let $V = \{v_1, v_2, \dots, v_v\}$ be the vertex set of the graph. By definition, for every vertex $v_i \in V$, its degree satisfies: $$m \leq \deg(v_i) \leq M$$
2. Summing this inequality over all $v$ vertices: $$\sum_{i=1}^v m \leq \sum_{i=1}^v \deg(v_i) \leq \sum_{i=1}^v M$$ $$v \cdot m \leq \sum_{i=1}^v \deg(v_i) \leq v \cdot M$$
3. By the Handshaking Lemma, the sum of all vertex degrees is equal to twice the number of edges: $$\sum_{i=1}^v \deg(v_i) = 2e$$
4. Substitute $2e$ into the inequality: $$v \cdot m \leq 2e \leq v \cdot M$$
5. Since $v > 0$, we divide the entire inequality by $v$: $$m \leq \frac{2e}{v} \leq M$$

Thus, the bounds hold. ∎

Goal: Determine the regularity conditions for standard graph families and compute the vertex count of a 4-regular graph with 10 edges.

Step-by-Step Analysis:

1. Regularity of Families:
   • $K_n$ is $(n-1)$-regular for all $n \geq 1$.
   • $C_n$ is 2-regular for all $n \geq 3$.
   • $W_n$ consists of a hub of degree $n$ and rim vertices of degree 3. For $W_n$ to be regular, we must have $n=3$. $W_3$ is isomorphic to $K_4$, which is 3-regular. Thus, $W_n$ is regular only if $n=3$.
   • $Q_n$ is $n$-regular for all $n \geq 1$.
   • $K_{m,n}$ is regular if and only if $m=n$ (it is then $n$-regular).
2. Calculation for 4-regular graph with $e=10$: Let $v = |V|$ be the number of vertices. Since the graph is 4-regular, the degree of every vertex is 4. Applying the Handshaking Lemma: $$4v = 2e \implies 4v = 2(10) = 20 \implies v = 5$$

Conclusion: The vertex count for the 4-regular graph with 10 edges is 5 (realized by $K_5$). ∎

Goal: Prove that the number of edges $e$ in any simple bipartite graph on $v$ vertices is at most $v^2/4$.

Proof:

1. Let $G = (V, E)$ be a simple bipartite graph. By definition, the vertex set can be partitioned into two disjoint subsets $V_1$ and $V_2$ of sizes $k$ and $v-k$, respectively, such that all edges connect a vertex in $V_1$ to a vertex in $V_2$.
2. The maximum possible number of edges in a simple bipartite graph is achieved when every vertex in $V_1$ is connected to every vertex in $V_2$ (a complete bipartite graph $K_{k, v-k}$): $$e \leq k(v-k)$$
3. We maximize the function $f(k) = k(v-k)$ over the real numbers. Using the Arithmetic Mean-Geometric Mean (AM-GM) inequality: $$\sqrt{k(v-k)} \leq \frac{k + (v-k)}{2} = \frac{v}{2}$$
4. Squaring both sides of the inequality: $$k(v-k) \leq \frac{v^2}{4}$$
5. Since $e \leq k(v-k)$, we conclude: $$e \leq \frac{v^2}{4}$$

This completes the proof. ∎

Goal: Prove that the number of vertices with odd degree in an undirected graph must be even.

Proof:

1. Let $G = (V, E)$ be an undirected graph. Partition the vertex set $V$ into two disjoint sets:
   • $V_e$: vertices with even degrees
   • $V_o$: vertices with odd degrees
2. Apply the Handshaking Lemma: $$\sum_{v \in V} \deg(v) = 2e$$
3. Split the sum into the two partitioned sets: $$\sum_{v \in V_e} \deg(v) + \sum_{v \in V_o} \deg(v) = 2e$$
4. Analyze the parities:
   • The right-hand side $2e$ is even.
   • The sum $\sum_{v \in V_e} \deg(v)$ is a sum of even integers, which must be even.
5. Rearranging the terms: $$\sum_{v \in V_o} \deg(v) = 2e - \sum_{v \in V_e} \deg(v)$$ Since the difference of two even numbers is even, the sum $\sum_{v \in V_o} \deg(v)$ must be even.
6. The sum $\sum_{v \in V_o} \deg(v)$ consists entirely of odd integers. A sum of odd integers is even if and only if it contains an even number of terms. Thus, the cardinality of $V_o$ must be even.

This completes the proof. ∎

Goal: Prove the bidirectional equivalence between a graph being bipartite and having no odd cycles.

Proof:

1. $(\Rightarrow)$ Assume $G$ is bipartite: Let $V_1, V_2$ be the bipartition of $V$. Suppose $G$ contains a cycle $C = v_0, v_1, v_2, \dots, v_k, v_0$. Without loss of generality, let $v_0 \in V_1$. Because edges only connect $V_1$ to $V_2$, the cycle path must alternate partitions: - $v_1 \in V_2$ - $v_2 \in V_1$ In general, $v_i \in V_1$ if $i$ is even, and $v_i \in V_2$ if $i$ is odd. Since $\{v_k, v_0\}$ is an edge and $v_0 \in V_1$, we must have $v_k \in V_2$, which requires $k$ to be odd. The cycle length is $k+1$. Since $k$ is odd, $k+1$ is even. Thus, all cycles in $G$ must be of even length, and no odd cycles can exist.
2. $(\Leftarrow)$ Assume $G$ has no odd cycles: Assume without loss of generality that $G$ is connected. Choose an arbitrary vertex $v_0 \in V$. For each $u \in V$, let $d(u)$ be the length of the shortest path from $v_0$ to $u$. Partition $V$ into two sets: - $V_1 = \{u \in V : d(u) \text{ is even}\}$ - $V_2 = \{u \in V : d(u) \text{ is odd}\}$ Suppose for contradiction that two adjacent vertices $x$ and $y$ lie in the same set, say $V_1$. Let $P_x$ and $P_y$ be the shortest paths from $v_0$ to $x$ and $y$, respectively. Let $z$ be the last common vertex on these paths. The path from $z$ to $x$ has length $d(x) - d(z)$, and the path from $z$ to $y$ has length $d(y) - d(z)$. Combining these paths with the edge $\{x, y\}$ forms a cycle of length: $$(d(x) - d(z)) + (d(y) - d(z)) + 1 = d(x) + d(y) - 2d(z) + 1$$ Since $d(x)$ and $d(y)$ are both even, their sum is even. Thus, the cycle length is $\text{even} - \text{even} + 1 = \text{odd}$. This contradicts the assumption that $G$ has no odd cycles. Thus, no adjacent vertices lie in the same set, proving $G$ is bipartite.

∎

Goal: Formally prove that the Königsberg bridges multigraph lacks an Euler path.

Proof:

1. Euler Path Condition: An undirected connected multigraph contains an Euler path if and only if it has exactly $0$ or $2$ vertices of odd degree.
2. Count odd-degree vertices: The degrees of the four vertices representing the landmasses are: $$\{3, 3, 3, 5\}$$ All four vertices have odd degree.
3. Since the number of odd-degree vertices is 4 (which is greater than 2), the graph fails the condition.

Conclusion: No Euler path exists in the Königsberg bridges multigraph. ∎

Goal: Determine the existence of Euler circuits/paths in $K_5$.

Step-by-Step Analysis:

1. Verify connectedness: $K_5$ is a complete graph, which is connected.
2. Verify degrees: In $K_5$, every vertex is connected to all other 4 vertices. Thus: $$\deg(v) = 4 \quad \text{for all } v \in V$$
3. Apply Euler's theorems: - A connected graph has an Euler circuit if and only if every vertex has an even degree. Since $4$ is even, an Euler circuit exists. - Since every Euler circuit is also a valid Euler path, an Euler path also exists.

∎

Goal: Analyze the existence of Euler circuits/paths in $K_4$.

Step-by-Step Analysis:

1. Check degrees: In $K_4$, each vertex is connected to all other 3 vertices. Thus: $$\deg(v) = 3 \quad \text{for all } v \in V$$
2. Count odd-degree vertices: All 4 vertices have odd degrees.
3. Apply Euler's conditions: - An Euler path requires exactly 0 or 2 vertices of odd degree. Since $K_4$ has 4, no Euler path exists. - An Euler circuit requires all vertices to have even degrees. Since they are odd, no Euler circuit exists.

∎

Goal: Identify the conditions on $m$ and $n$ for $K_{m,n}$ to have a Hamiltonian cycle.

Proof:

1. Let $V_1, V_2$ be the bipartition of $K_{m,n}$ with $|V_1| = m$ and $|V_2| = n$. A Hamiltonian cycle must visit every vertex in $V_1 \cup V_2$ exactly once and return to the starting vertex.
2. Any path or cycle in a bipartite graph must alternate between partitions: $$v_1 \to v_2 \to v_3 \to v_4 \to \dots \to v_1$$ where $v_1, v_3, \dots \in V_1$ and $v_2, v_4, \dots \in V_2$.
3. To form a closed cycle that alternates partitions, the cycle must visit an equal number of vertices in $V_1$ and $V_2$. Because the cycle must be Hamiltonian (visiting *all* vertices), the size of the partitions must be equal: $$m = n$$
4. To avoid trivial paths (like $K_{1,1}$ which is a single edge with no cycles), we also require $m, n \geq 2$.

Conclusion: $K_{m,n}$ contains a Hamiltonian cycle if and only if $m = n \geq 2$. ∎

Goal: Prove the existence of a Hamiltonian cycle in $Q_n$ for $n \geq 2$.

Proof:

1. Gray Code Correspondence: A Hamiltonian cycle in $Q_n$ corresponds to a cyclic sequence of all $2^n$ binary strings of length $n$ such that adjacent strings differ in exactly 1 bit. Such a sequence is a Reflected Gray Code.
2. Inductive Construction: We prove the existence of such a code by induction on $n \geq 2$.
   • Base Case ($n=2$): $Q_2$ is a cycle $C_4$. The cycle sequence is: $$00 \to 01 \to 11 \to 10 \to 00$$ Adjacent strings differ in 1 bit, and the last differs from the first in 1 bit.
   • Inductive Step: Assume $Q_{n-1}$ has a Hamiltonian cycle represented by the sequence $G_{n-1} = (g_1, g_2, \dots, g_{2^{n-1}})$. We construct a sequence $G_n$ of length $2^n$ for $Q_n$: $$G_n = (0g_1, 0g_2, \dots, 0g_{2^{n-1}}, 1g_{2^{n-1}}, 1g_{2^{n-1}-1}, \dots, 1g_1)$$ - The first half consists of $G_{n-1}$ prefixed by $0$. Adjacent elements differ in 1 bit. - The second half consists of $G_{n-1}$ in reverse order prefixed by $1$. Adjacent elements differ in 1 bit. - The transition from $0g_{2^{n-1}}$ to $1g_{2^{n-1}}$ is a change in 1 bit (the first bit). - The transition from the end $1g_1$ to the start $0g_1$ is a change in 1 bit (the first bit).
   This forms a valid Hamiltonian cycle in $Q_n$.

∎

Goal: Formulate an algorithm using traversals (BFS/DFS) to count the connected components of a graph.

Step-by-Step Algorithm:

1. Initialize a boolean array `visited` of size $|V|$ to `false` for all vertices. Initialize a counter `components = 0`.
2. For each vertex $v \in V$: - If `visited[v]` is `false`: - Increment `components` by 1. - Start a BFS or DFS traversal originating at $v$. - During the traversal, mark every reached vertex $u$ as `visited[u] = true`.
3. Return `components` as the total number of connected components.

Complexity Analysis: - Each vertex is visited exactly once when checking the loop or during traversal. - In the adjacency list representation, each edge is examined exactly twice (once from each endpoint). - The total time complexity is $O(|V| + |E|)$. ∎

Goal: Prove that removing any non-leaf vertex from a tree disconnects the graph.

Proof:

1. Let $T = (V, E)$ be a tree. A tree is a connected, acyclic graph. A crucial property of trees is that for any two vertices $x, y \in V$, there exists a unique simple path between them.
2. Let $v$ be an internal vertex of $T$. By definition, an internal vertex has a degree of at least 2. Let $u$ and $w$ be two distinct neighbors of $v$ in $T$.
3. Since $u$ and $w$ are adjacent to $v$, the unique path between $u$ and $w$ in $T$ must be $u - v - w$. If there were another path between $u$ and $w$ that did not pass through $v$, the combination of these two paths would form a cycle, contradicting the acyclic property of trees.
4. If we remove vertex $v$ to form the subgraph $T - \{v\}$, the path $u - v - w$ is destroyed. Since this path was unique, no path between $u$ and $w$ remains in $T - \{v\}$.
5. Thus, $T - \{v\}$ is disconnected, which by definition makes $v$ a cut vertex.

This completes the proof. ∎

Goal: Use Hall's Marriage Theorem to verify the existence of a perfect matching.

Step-by-Step Analysis:

1. Let $S = \{S_1, S_2, S_3, S_4\}$ and $P = \{P_1, P_2, P_3, P_4\}$. We check Hall's Condition: for every subset $A \subseteq S$, its neighborhood $|N(A)| \geq |A|$.
2. Evaluate all subsets $A$ of $S$: - Size 1: Each student prefers at least 2 projects, so $|N(A)| \geq 2 \geq 1$ for all singletons. ✓ - Size 2: - $\{S_1, S_2\} \to N = \{P_1, P_2, P_3\}$, size $3 \geq 2$ ✓ - $\{S_2, S_3\} \to N = \{P_2, P_3, P_4\}$, size $3 \geq 2$ ✓ - $\{S_3, S_4\} \to N = \{P_1, P_3, P_4\}$, size $3 \geq 2$ ✓ - $\{S_1, S_4\} \to N = \{P_1, P_2, P_4\}$, size $3 \geq 2$ ✓ - $\{S_1, S_3\} \to N = \{P_1, P_2, P_3, P_4\}$, size $4 \geq 2$ ✓ - $\{S_2, S_4\} \to N = \{P_1, P_2, P_3, P_4\}$, size $4 \geq 2$ ✓ - Size 3: Any subset of size 3 contains neighbors spanning all 4 projects (size $4 \geq 3$). ✓ - Size 4: $N(S) = \{P_1, P_2, P_3, P_4\}$, size $4 \geq 4$. ✓
3. Since the condition holds for all subsets, a perfect matching exists.
4. Matching construction: - Match $S_1 \to P_1$ - Match $S_2 \to P_2$ - Match $S_3 \to P_3$ - Match $S_4 \to P_4$

Conclusion: A perfect matching exists. ∎

Goal: Determine the existence of a perfect matching for the updated preferences.

Step-by-Step Analysis:

1. We test Hall's Condition on the subset $A = \{S_1, S_2\} \subseteq S$.
2. Find the neighborhood of $A$: $$N(A) = N(S_1) \cup N(S_2) = \{P_1\} \cup \{P_1\} = \{P_1\}$$
3. Compare sizes: $$|A| = 2, \quad |N(A)| = 1$$ Here, $|N(A)| < |A|$, which violates Hall's Condition.
4. Intuitively, both students $S_1$ and $S_2$ only prefer project $P_1$. Since $P_1$ can only be assigned to one student, it is impossible to satisfy both.

Conclusion: No perfect matching exists because Hall's Condition is violated. ∎