AI Solution AGT END 23-24

1

1(a) ✅

1(a) https://www.youtube.com/watch?v=pGe2uSidWEY

Okay, let’s use the video to walk through the proof that $\chi (G)\le \Delta (G)+1$.

(Video 0:03 - 0:17) The video starts by stating the Theorem: For any graph G, the chromatic number $\chi (G)$ (the minimum number of colours needed for a proper vertex colouring) is less than or equal to $\Delta (G)+1$ (the maximum degree of any vertex in G, plus one).

(Video 0:37 - 0:41) The proof method is Induction on n, where n is the number of vertices in the graph.

(Video 0:57 - 1:22) Base Case: We start with the smallest possible graph, $n=1$.

• This graph is just a single vertex ($K_1$).
• You need only 1 colour to colour it ($\chi (K_1)=1$).
• The maximum degree is 0, since there are no edges ($\Delta (K_1)=0$).
• The theorem says $\chi (G)\le \Delta (G)+1$. For $K_1$, this is $1\le 0+1$, which is true. The base case holds.

(Video 1:22 - 1:33) Inductive Hypothesis (IH): We assume the theorem is true for all graphs that have $n-1$ vertices. That is, we assume that for any graph $H$ with $n-1$ vertices, we know $\chi (H)\le \Delta (H)+1$.

(Video 1:33 - 4:17) - Inductive Step: Now, we need to prove the theorem is true for a graph $G$ with $n$ vertices, using the assumption (IH) about graphs with $n-1$ vertices.

1. (1:41 - 1:58) Take any graph $G$ with $n$ vertices. Pick any vertex $v$ from $G$. Consider the graph $G-v$ (the graph $G$ with vertex $v$ and all edges connected to it removed). $G-v$ has $n-1$ vertices.

2. (1:58 - 2:22) Since $G-v$ has $n-1$ vertices, we can apply the Inductive Hypothesis to it. The IH tells us that $G-v$ can be coloured with at most $\Delta (G-v)+1$ colours. Let’s imagine we have such a valid colouring for all vertices in $G-v$.

3. (2:22 - 2:59) Now, we add the vertex $v$ back. We need to assign a colour to $v$. The only rule is that $v$‘s colour must be different from the colours of its neighbours.

   • How many neighbours does $v$ have in the original graph G? It has $de{g}_G(v)$ neighbours.
   • We know $de{g}_G(v)$ must be less than or equal to the maximum degree in G, i.e., $de{g}_G(v)\le \Delta (G)$.
   • So, vertex $v$ has at most $\Delta (G)$ neighbours. These neighbours are already coloured (since they are in $G-v$).

4. (3:00 - 4:15) The neighbours of $v$ use up at most $\Delta (G)$ colours from the available pool. We need to show we have enough colours total so there’s always one left for $v$. The video considers two cases based on how $\Delta (G)$ relates to $\Delta (G-v)$:

   • Case 1 (Video 3:04 - 3:36): $\Delta (G)=\Delta (G-v)$

     • From step 2, we know $G-v$ can be coloured with at most $\Delta (G-v)+1$ colours. Since $\Delta (G-v)=\Delta (G)$, this means $G-v$ uses at most $\Delta (G)+1$ colours. Let’s consider this set of $\Delta (G)+1$ colours as our palette.
     • The neighbours of $v$ forbid at most $\Delta (G)$ colours from this palette.
     • Since we have $\Delta (G)+1$ colours available in the palette and at most $\Delta (G)$ are forbidden by neighbours, there is at least one colour left in the palette that we can assign to $v$.
     • Assign that available colour to $v$. Now the entire graph $G$ is coloured using at most $\Delta (G)+1$ colours. The theorem holds for this case.

   • Case 2 (Video 3:37 - 4:15): $\Delta (G)\ne \Delta (G-v)$

     • If the maximum degrees aren’t equal, removing $v$ must have lowered the maximum degree. So, $\Delta (G-v)<\Delta (G)$. This means $\Delta (G-v)\le \Delta (G)-1$.
     • From step 2, we know $G-v$ can be coloured using at most $\Delta (G-v)+1$ colours.
     • The video’s logic (3:51): Let’s colour $G-v$ (using $\le \Delta (G-v)+1$ colours) and then use a completely new colour just for $v$.
     • How many colours did we use in total? We used (colours for $G-v$) + 1 (for $v$). This is $\le (\Delta (G-v)+1)+1=\Delta (G-v)+2$.
     • Now substitute the inequality from the start of this case: Total colours $\le (\Delta (G)-1)+2=\Delta (G)+1$.
     • So, even by using a potentially new colour for $v$, we still only needed at most $\Delta (G)+1$ colours for the whole graph $G$. The theorem holds for this case too.

(Video 4:15 - 4:17) Conclusion: Since the theorem holds for both possible cases, the inductive step is complete. By the principle of mathematical induction, the theorem $\chi (G)\le \Delta (G)+1$ is true for all graphs $G$.

(Video 4:24 - End) The video then discusses examples like complete graphs ($K_n$) and odd cycles ($C_{2k+1}$) where equality holds ($\chi (G)=\Delta (G)+1$), proving the bound is “tight” in general. It also mentions Brooks’ Theorem, which states that for most other graphs, you can actually do better: $\chi (G)\le \Delta (G)$.

1(b) ✅

b. Prove that G is bipartite iff the chromatic number of G is 2. (Solution from page 8, 43)

Direction 1: If G is bipartite, then $\chi (G)=2$. ($\Rightarrow$)

1. Assume G is bipartite: What does this mean by definition? It means we can split all the vertices $V$ into two separate groups, let’s call them $X$ and $Y$, such that:

   • Every vertex is in either $X$ or $Y$, and no vertex is in both ($V=X\cup Y$, $X\cap Y=\varnothing$).
   • Crucially, all edges in the graph only connect a vertex from group $X$ to a vertex from group $Y$. There are no edges connecting two vertices within $X$, and no edges connecting two vertices within $Y$.

2. Show $\chi (G)=2$: We need to show that the minimum number of colors needed is 2.

   • Can we color it with 2 colors? Yes! Use the partition $X$ and $Y$. Assign Color 1 to all vertices in group $X$. Assign Color 2 to all vertices in group $Y$.
   • Is this a proper coloring? Consider any edge $e=(u,v)$. Since G is bipartite with partition $X,Y$, one endpoint (say $u$) must be in $X$ and the other ($v$) must be in $Y$. So $u$ gets Color 1 and $v$ gets Color 2. Since the colors are different, the edge $(u,v)$ is properly colored. This applies to all edges.
   • Can we use fewer than 2 colors? If the graph has at least one edge (which is implied by “non-trivial graph” or if $\chi (G)=2$), then we need at least 2 colors. We cannot use just 1 color.
   • Conclusion for Direction 1: Since we found a proper coloring with exactly 2 colors, and we can’t use fewer, the minimum number of colors needed ($\chi (G)$) is exactly 2.

Direction 2: If $\chi (G)=2$, then G is bipartite. ($\Leftarrow$)

1. Assume $\chi (G)=2$: What does this mean? It means there exists a proper coloring of G using exactly two colors (say, Color 1 and Color 2).
2. Construct the partition: Use this coloring to define our sets $X$ and $Y$. Let $X$ be the set of all vertices colored with Color 1. Let $Y$ be the set of all vertices colored with Color 2.
3. Show it’s a bipartite partition:
   • Does $X\cup Y=V$? Yes, every vertex received one of the two colors.
   • Is $X\cap Y=\varnothing$? Yes, no vertex can have both colors.
   • Are there edges within X? No. If an edge $(u,v)$ existed with both $u,v\in X$, then both $u$ and $v$ would have Color 1. But since the coloring is proper, adjacent vertices must have different colors. So, no edge can exist within $X$.
   • Are there edges within Y? No, for the same reason (both would have Color 2, violating proper coloring).
4. Conclusion for Direction 2 (Direct): Since we constructed a partition $(X,Y)$ of the vertices $V$ such that there are no edges within $X$ and no edges within $Y$, the graph G fits the definition of a bipartite graph.

2

Q2 (Page 1)

2(a) ✅

a. The Prufer sequence S of a labelled tree T is S= {1, 7, 6, 6, 1}. Draw the tree T describing all the intermediate steps pictorially during the process. (Solution from pages 9-17, 37)

Length = 5 $⟹n=7$. $L=\{1,2,3,4,5,6,7\}$.

1. $S=\{1,7,6,6,1\}$, $L=\{1,2,3,4,5,6,7\}$. Smallest $x\in L\setminus S=2$. Join 2 to $a_1=1$. Edge (2,1). $S=\{7,6,6,1\}$, $L=\{1,3,4,5,6,7\}$.
2. $S=\{7,6,6,1\}$, $L=\{1,3,4,5,6,7\}$. Smallest $x\in L\setminus S=3$. Join 3 to $a_1=7$. Edge (3,7). $S=\{6,6,1\}$, $L=\{1,4,5,6,7\}$.
3. $S=\{6,6,1\}$, $L=\{1,4,5,6,7\}$. Smallest $x\in L\setminus S=4$. Join 4 to $a_1=6$. Edge (4,6). $S=\{6,1\}$, $L=\{1,5,6,7\}$.
4. $S=\{6,1\}$, $L=\{1,5,6,7\}$. Smallest $x\in L\setminus S=5$. Join 5 to $a_1=6$. Edge (5,6). $S=\{1\}$, $L=\{1,6,7\}$.
5. $S=\{1\}$, $L=\{1,6,7\}$. Smallest $x\in L\setminus S=7$. Join 7 to $a_1=1$. Edge (7,1). $S=\{\}$, $L=\{1,6\}$.
6. Remaining L = {1, 6}. Join 1 to 6. Edge (1,6).

Final Edges: {(2,1), (3,7), (4,6), (5,6), (7,1), (1,6)}. Tree T:

graph TD
    1 --- 2;
    1 --- 6;
    1 --- 7;
    7 --- 3;
    6 --- 4;
    6 --- 5;

2(b) ✅

b. Write the algorithm of the same. (Solution from pages 9-11, 37)

Algorithm: Prufer Sequence S to Labelled Tree T Input: $S=(a_1,a_2,...,a_{n-2})$, $a_i\in \{1,...,n\}$. Output: Edges of T.

1. $L=\{1,...,n\}$. $E=\{\}$.
2. While $S$ is not empty:
   • Find smallest $x\in L$ such that $x\notin S$.
   • Join $x$ to $a_1$ (first element of $S$). Add $(x,a_1)$ to $E$.
   • Delete $a_1$ from $S$. Delete $x$ from $L$.
3. Join the remaining 2 items in $L$ via an edge. Add to $E$.
4. Return $E$.

---

3

Q3 (Page 1)

3(a) ✅

a. Prove by method of induction that a graph G is a tree iff G is acyclic and the number of edges m in G is equal to n-1, where n is the number of vertices in G. (Solution from page 18-19, 35) Okay, let’s break down the proof shown in the video (which corresponds to Q3.a on your exam sheet) step-by-step.

The Theorem (stated at 0:59): A graph G is a tree if and only if ($⟺$) G is acyclic and the number of edges ($m$) equals the number of vertices ($n$) minus 1 ($m=n-1$).

Because it’s an “if and only if” statement, we need to prove two things:

Part 1: ($⟹$) If G is a tree, then G is acyclic and $m=n-1$. (Video 2:05 - 7:37)

1. Acyclicity: If G is a tree, it must be acyclic. This is part of the definition of a tree (a tree is a connected, acyclic graph). The video confirms this around 2:16 - 2:27. (Check mark for acyclic part!)
2. Prove m = n-1: The video proves this using induction on the number of vertices (n).
   • Base Case (n=1): (Video 3:01) If a tree has only 1 vertex, it has 0 edges. $n=1,m=0$. The formula $m=n-1$ becomes $0=1-1$, which is true. So the base case holds.
   • Inductive Hypothesis (IH): (Video 3:30) Assume that for all trees with fewer than $n$ vertices (specifically, for trees with $n-1$ vertices, assuming $n\ge 2$), the formula holds (i.e., they have $(n-1)-1=n-2$ edges). The video states it slightly differently but means the same: “Suppose all trees of order n have n-1 edges” - this is assuming the statement holds for the step before the one we’re trying to prove.
   • Inductive Step (Prove for n vertices): (Video 4:11 onwards)
     • Take any tree T with $n$ vertices ($n\ge 2$).
     • Fact: Every tree with $n\ge 2$ vertices must have at least two “leaves” (vertices with degree 1). (Video 4:55 - 5:03).
     • Pick one leaf vertex, call it $v$. (Video 5:20).
     • Consider the graph $T^{\prime }=T-v$ (remove the vertex $v$ and the single edge connected to it). (Video 5:52).
     • $T^{\prime }$ is still connected and has no cycles (removing a leaf doesn’t disconnect a tree or create cycles). So, $T^{\prime }$ is also a tree.
     • $T^{\prime }$ has $n-1$ vertices.
     • Apply the IH to $T^{\prime }$: Since $T^{\prime }$ is a tree with $n-1$ vertices, by our assumption (IH), $T^{\prime }$ must have $(n-1)-1=n-2$ edges. (Video 6:10 - 6:32).
     • Relate back to T: How many edges does the original tree T have? It has all the edges of $T^{\prime }$ plus the one edge we removed with $v$. So, T has $(n-2)+1=n-1$ edges. (Video 6:44 - 7:07).
   • Conclusion for Part 1: We’ve shown that if G is a tree, it’s acyclic (by definition) and it has $m=n-1$ edges (by induction).

Part 2: ($⟸$) If G is acyclic and $m=n-1$, then G is a tree. (Video 7:57 - 13:19)

1. Goal: We are given G is acyclic and $m=n-1$. To show G is a tree, we only need to show G is also connected. (The definition of a tree is connected + acyclic).
2. Strategy: Let’s see what properties G must have given it’s acyclic and $m=n-1$. Consider the connected components of G. Maybe G isn’t connected, maybe it looks like several separate pieces. Let’s say there are $k$ connected components: $G_1,G_2,...,G_k$. (Video 8:40).
3. Properties of Components:
   • Each component $G_i$ is connected (by definition).
   • Each component $G_i$ must be acyclic (because the whole graph G is acyclic).
   • Therefore, each component $G_i$ is itself a tree! (Video 9:50 - 10:22).
4. Counting Edges:
   • Let component $G_i$ have $n_i$ vertices and $m_i$ edges.
   • Since each $G_i$ is a tree, we can apply the result from Part 1 to it: for each component $i$, $m_i=n_i-1$. (Video 10:26).
   • The total number of edges in the whole graph G is $m=m_1+m_2+...+m_k={\sum }_{i=1}^k{m}_i$. (Video 11:14).
   • Substitute $m_i=n_i-1$: $m={\sum }_{i=1}^k(n_i-1)$.
   • Split the sum: $m=({\sum }_{i=1}^k{n}_i)-({\sum }_{i=1}^{k}1)$.
   • The sum of vertices in all components ($\sum n_i$) is just the total number of vertices in G, which is $n$.
   • The sum of ‘1’ k times ($\sum 1$) is just $k$.
   • So, we found that $m=n-k$. (Video 12:01).
5. Contradiction/Conclusion:
   • We were given in this part of the proof that $m=n-1$.
   • But we just calculated from the component properties that $m=n-k$.
   • So, it must be that $n-1=n-k$. This can only be true if $k=1$. (Video 12:43).
   • What does $k=1$ mean? It means there was only one connected component to begin with.
   • Therefore, the graph G must be connected.
6. Final step for Part 2: We were given G is acyclic, and we just proved it must be connected. An acyclic, connected graph is, by definition, a tree.

Overall Conclusion: Since we proved both directions ($⟹$ and $⟸$), the theorem is true. A graph is a tree if and only if it is acyclic and has $n-1$ edges.

3(b) ❌

b. Deduce that clique decision problem is NP-Hard using Satisfiability problem. (Solution from pages 20-25, 50-51)

Show SAT $\propto$ CDP. Given 3-SAT formula $F={\wedge }_{i=1}^k{C}_i$, $C_i=(l_{i1}\vee l_{i2}\vee l_{i3})$. Construct Graph $G=(V,E)$:

• $V=\{v_{ij}\mid l_{ij}\text{ is the }j\text{-th literal in clause }{C}_i\}$.
• $E=\{(v_{ij},v_{pq})\mid i\ne p\text{ and }{l}_{ij}\ne {\bar{l}}_{pq}\}$. (Edges between literals in different clauses, unless they are contradictory). Claim: $F$ is satisfiable $⟺$ G has a clique of size $k$.
• ($⟹$) If F is satisfiable, pick one true literal $l_{i,j_i}$ from each clause $C_i$. The corresponding vertices $v_{i,j_i}$ form a k-clique because they are from different clauses ($i\ne p$) and cannot be contradictory (otherwise F wouldn’t be satisfied).
• ($⟸$) If G has a k-clique $K$, it must contain exactly one vertex $v_{i,j_i}$ from each clause group $i$. The literals $l_{i,j_i}$ corresponding to vertices in $K$ form a consistent partial assignment (no $x_r$ and ${\bar{x}}_r$ appear, as there’s no edge between them). Set these literals to True. This satisfies F. Since SAT is NP-Complete and SAT $\propto$ CDP, CDP is NP-Hard.

---

4

Q4 (Page 1)

4(a) ✅

a. Prove that for a simple graph G with n number of vertices ($n\ge 4$), and E number of edges and genus g satisfies $g\ge \lceil \frac{1}{6}(|E|-3n)+1\rceil$. (Solution from page 26)

Proof: Every face of an embedding on genus $g$ surface has $\ge 3$ edges. ${\sum }_{\text{faces}}\text{length}(F)=2|E|$. So $3f\le 2|E|$, $f\le \frac{2}{3}|E|$. Euler’s formula for genus g: $n-|E|+f=2-2g$. $f=|E|-n+2-2g$. Substitute: $|E|-n+2-2g\le \frac{2}{3}|E|$ $3|E|-3n+6-6g\le 2|E|$ $|E|-3n+6\le 6g$ $g\ge \frac{1}{6}(|E|-3n+6)=\frac{1}{6}(|E|-3n)+1$. Since g is integer, $g\ge \lceil \frac{1}{6}(|E|-3n)+1\rceil$. $✓$

4(b) ❌

b. “A necessary and sufficient condition for a graph G to be planar is that for every circuit C of G the auxiliary graph G+(C) is bipartite”, prove it. (Solution from page 27)

Proof:

• ($⟹$) Necessary: Assume G is planar. Embed G. Any circuit C divides plane into Interior/Exterior. Any bridge B of C lies entirely in Int or Ext. Vertices of $G^{+}(C)$ are bridges. Edge between bridges if incompatible. Partition bridges into $B_{in}$ (in Int) and $B_{out}$ (in Ext). No two bridges in $B_{in}$ are incompatible (no edge within $B_{in}$). No two bridges in $B_{out}$ are incompatible (no edge within $B_{out}$). Hence $G^{+}(C)$ is bipartite. $✓$
• ($⟸$) Sufficient (Contrapositive): Assume G is not planar. By Kuratowski, G contains $K_5$ or $K_{3,3}$ subdivision.
  • Case $K_{3,3}$: Choose circuit C = 6-cycle. The 3 remaining path-bridges are pairwise incompatible. $G^{+}(C)=K_3$, not bipartite.
  • Case $K_5$: Choose circuit C = 5-cycle. The 5 path-bridges form $K_5$ structure. Can find 3 mutually incompatible bridges. $G^{+}(C)$ contains $K_3$, not bipartite. If G is non-planar, $\exists C$ such that $G^{+}(C)$ is not bipartite. $✓$

---

5

Q5 (Page 2)

5(a) ❌

a. Suppose want to schedule some final exams… How many exam slots are necessary? (Solution from pages 32-36)

Model as Graph Coloring: Vertices $V=\{1,2,...,8\}$ for courses. Edge $(i,j)$ if courses conflict. No edge if listed as non-conflicting. Non-conflicting pairs (no edge): (1,2), (1,4), (1,3), (2,3), (1,7), (2,7), (1,8), (2,8), (3,8), (1,5), (2,5), (4,5), (1,6), (2,6), (4,6), (5,6). Edges (conflicts): {(2,4), (3,4), (3,5), (3,6), (3,7), (4,7), (4,8), (5,7), (5,8), (6,7), (6,8), (7,8)}. Find $\chi (G)$. Coloring (from slides):

• Slot 1 (Red): {3, 5, 8} (Slide shows 3, 5 colored red)
• Slot 2 (Green): {4, 6, 7} (Slide shows 4, 6, 7 green)
• Slot 3 (Blue): {1, 2} (Slide shows 1, 2 blue) Wait, slide 36 shows a 3-coloring: Slot 1 {3137, 1007}, Slot 2 {3203, 3261, 4115}, Slot 3 {3157, 4156, 4118}. Let’s redo coloring for this problem:

1. 1: Color 1
2. 2: (1,2) no edge → Color 1
3. 3: (1,3) (2,3) no edge → Color 1
4. 4: Edges (2,4), (3,4). Conflicts C1. → Color 2
5. 5: Edge (3,5). Conflicts C1. No edge (4,5). → Color 2
6. 6: Edge (3,6). No edge (4,6), (5,6). Conflicts C1. → Color 2
7. 7: Edges (3,7), (4,7), (5,7), (6,7). Conflicts C1, C2. → Color 3
8. 8: Edges (4,8), (5,8), (6,8), (7,8). Conflicts C2, C3. No edge (1,8), (2,8), (3,8). → Color 1 Colors used: 3. $\chi (G)=3$ (e.g., clique {3, 4, 7}). Answer: 3 exam slots are necessary.

5(b) ✅

b. Illustrate with an example that any graph is a subgraph of a r-regular graph. (Solution from pages 37-41, 48)

König Theorm

Theorem (König): Every graph $G$ with maximum degree $\Delta (G)=r$ is an induced subgraph of some $r$-regular graph $H$.

Proof Idea (Constructive):

The proof constructs the $r$-regular graph $H$ iteratively.

1. Base Case: If the given graph $G$ is already $r$-regular, then $H=G$, and $G$ is an induced subgraph of itself. We are done.

2. Inductive Step: If $G$ is not $r$-regular, it must contain at least one vertex $v$ with degree $de{g}_G(v)<r$. (Specifically, the minimum degree $\delta (G)<r$).

   • Take two identical copies of the current graph (let’s call it $G_i$, starting with $G_0=G$). Call the copies $G_i$ and $G_i^{\prime }$.
   • For every vertex $v$ in $G_i$ such that $de{g}_{G_i}(v)<r$, add an edge between $v$ in $G_i$ and its corresponding vertex $v^{\prime }$ in $G_i^{\prime }$.
   • Call the resulting graph $G_{i+1}$. Note that the original $G$ is an induced subgraph of $G_{i+1}$.
   • The degrees of the vertices that had degree $<r$ in $G_i$ increase by 1 in $G_{i+1}$. Vertices that already had degree $r$ remain unchanged.
   • If $G_{i+1}$ is $r$-regular, we stop, and $H=G_{i+1}$.
   • If $G_{i+1}$ is still not $r$-regular (meaning its new minimum degree is still $<r$), repeat this step with $G_{i+1}$.

3. Termination: This process must terminate because, in each step, we increase the degrees of the lowest-degree vertices. Eventually, all vertices will reach degree $r$. The video suggests this occurs after $k=r-\delta (G)$ iterations, resulting in a graph $G_k$ which is $r$-regular and contains the original $G$ as an induced subgraph.

Link to original

6

6(a) ✅

a. If a graph G is maximal planar graph with n vertices (n>=3) and m edges then show that m = 3n – 6. (Solution from page 42, 56)

Solution: Take a plane drawing of G with $r$ regions. Since G is maximal planar, the boundary of every region is a triangle. Consider ${\sum }_{\text{all regions R}}$ (# edges on boundary R). Since each region is a triangle, this sum is $3r$. Also, each edge is on the boundary of exactly 2 regions, so each edge is counted twice in the sum. Thus the sum is $2m$. Therefore, $3r=2m$. By Euler’s Formula for plane graphs, $n-m+r=2$. Substituting $r=\frac{2m}{3}$ into Euler’s Formula gives $n-m+\frac{2m}{3}=2$. Multiplying by 3: $3n-3m+2m=6$. Simplifying: $3n-m=6$. Rearranging gives $m=3n-6$.

6(b) ✅

b. For a polyhedron with N number of vertices, E number of edges and F number of faces, prove by method of induction that N – E + F = 2. (Solution from pages 43-44, 58-59)

Proof: (Induction on $m=E$). Let $n=N,f=F$. Prove $n-m+f=2$.

• Basis: $m=0$. $n=1,f=1$. $1-0+1=2$. $✓$
• Ind. Hyp: Assume $n^{\prime }-m^{\prime }+f^{\prime }=2$ for connected planar graphs with $m^{\prime }<m$.
• Ind. Step: Let G be connected planar with m edges.
  • Case 1: G is a tree. $m=n-1,f=1$. $n-(n-1)+1=2$. $✓$
  • Case 2: G is not a tree. Let $e$ be an edge in a cycle. $G^{\prime }=G-e$. $G^{\prime }$ is connected. $n^{\prime }=n,m^{\prime }=m-1,f^{\prime }=f-1$. By IH, $n^{\prime }-m^{\prime }+f^{\prime }=2$. So $n-(m-1)+(f-1)=2⟹n-m+f=2$. $✓$ By induction, holds for all connected planar graphs.

---

7

Q7 (Page 2)

a. Why running time measurement is important to study? Mention some of the factors affecting the running time of a program. (Solution page 49 mentions ‘open question’)

(Based on general knowledge as solution is not provided) Importance: Predict performance, compare algorithms, assess feasibility, identify bottlenecks, manage resources. Factors: Algorithm design (complexity), input size, input characteristics, hardware (CPU, memory), software environment (OS, compiler, language).

b. Prove that every planar graph has a dual. (Solution page 49 mentions ‘Solved as theorem in Alan Gibson Book’)

(Based on standard construction as solution is not provided) Construction: Given a plane embedding of G.

1. Place a vertex $f^{\ast }$ in each face $f$ of G. These are vertices of the dual $G^{\ast }$.
2. For each edge $e$ separating faces $f_1$ and $f_2$ in G, draw an edge $e^{\ast }$ connecting $f_1^{\ast }$ and $f_2^{\ast }$ crossing only $e$. These are edges of $G^{\ast }$. This constructs the dual graph $G^{\ast }$.

---

8

Q8 (Page 2)

a. Discuss the merits and demits of Dijkstra’s Algorithm and Bellman-Ford Algorithm with examples. (Solution page 45 shows example graphs)

• Dijkstra:
  • Merits: Faster ($O(E\log V)$ or $O(V^2)$), conceptually simpler (greedy).
  • Demerits: Fails with negative edge weights, cannot detect negative cycles.
  • Example: Works on first graph (page 45), fails on second graph (page 45).
• Bellman-Ford:
  • Merits: Handles negative edge weights, detects negative cycles.
  • Demerits: Slower ($O(VE)$), cannot find shortest paths if negative cycles exist (but reports them).
  • Example: Works on first two graphs (page 45), detects negative cycle in third graph (page 45).

b. Use Prim’s algorithm to find a minimum spanning tree that takes the following graph as input. (Question on Page 3, Solution on Pages 28-31)

Graph: Vertices A, B, C, D, E, F. Edges with weights. Prim’s Steps (Start C):

1. Select C. Edges: (C,B,2), (C,E,2), (C,D,3), (C,A,4).
2. Add (C,B,2). MST = {(C,B)}. Consider edges from B: (B,A,4). Min edge is (C,E,2).
3. Add (C,E,2). MST = {(C,B), (C,E)}. Consider edges from E: (E,D,4), (E,F,3). Min edge is (C,D,3) or (E,F,3).
4. Add (E,F,3). MST = {(C,B), (C,E), (E,F)}. Consider edges from F: (F,D,3). Min edge is (C,D,3) or (F,D,3).
5. Add (C,D,3). MST = {(C,B), (C,E), (E,F), (C,D)}. Consider edges from D: (D,A,4). Min edge is (C,A,4), (B,A,4) or (D,A,4).
6. Add (C,A,4). MST = {(C,B), (C,E), (E,F), (C,D), (C,A)}. All vertices included.

Result: MST Edges = {(C,B), (C,E), (E,F), (C,D), (C,A)}. Total Weight = $2+2+3+3+4=14$.

---

9

Q9 (Page 3)

a. Find the all pairs shortest paths among all vertices for the following graph using Floyd-Warshall Algorithm (showing all intermediate steps) (Solution on page 48)

Graph vertices {1, 2, 3, 4}. Adjacency (assume weight 1 if edge exists, $\infty$ if not, 0 diagonal): $D^0=\left(\begin{array}{cccc}0& 1& \infty & 1\\ 1& 0& 1& \infty \\ \infty & 1& 0& 1\\ 1& \infty & 1& 0\end{array}\right)$ $D^1=\left(\begin{array}{cccc}0& 1& \infty & 1\\ 1& 0& 1& 2\\ \infty & 1& 0& 1\\ 1& 2& 1& 0\end{array}\right)$ (via k=1: $D^1[2,4]=1+1=2,D^1[4,2]=1+1=2$) $D^2=\left(\begin{array}{cccc}0& 1& 2& 1\\ 1& 0& 1& 2\\ 2& 1& 0& 1\\ 1& 2& 1& 0\end{array}\right)$ (via k=2: $D^2[1,3]=1+1=2,D^2[3,1]=1+1=2$) $D^3=D^2$ (via k=3: no changes) $D^4=D^3$ (via k=4: no changes)

Final Matrix: $D=\left(\begin{array}{cccc}0& 1& 2& 1\\ 1& 0& 1& 2\\ 2& 1& 0& 1\\ 1& 2& 1& 0\end{array}\right)$

b. Prove that Peterson Graph is non-planar using Kuratowski’s and Wagner’s Theorem as well. (Solution on pages 46-47, 49)

Peterson Graph (PG): 10 vertices, 15 edges. 1. Kuratowski’s Theorem: (Non-planar $⟺$ contains subdivision of $K_5$ or $K_{3,3}$)

• Proof 1: PG contains a subdivision of $K_{3,3}$. (Diagram on page 46 shows highlighted vertices/edges forming the subdivision).

2. Wagner’s Theorem: (Non-planar $⟺$ contains $K_5$ or $K_{3,3}$ minor)

• Proof 2: PG has a $K_5$ minor. Contract the 5 edges $e_1,...,e_5$ joining the outer cycle to the inner star. The resulting graph (page 47) has 5 vertices and is isomorphic to $K_5$.

$\therefore$ Peterson Graph is non-planar.

---

10

Q10 (Page 4)

a. Find the maximum flow through the given network using Ford-Fulkerson algorithm. (Solution on pages 60-62, 52)

Network with Source=1, Sink=7. Augmenting Paths:

1. Path: 1-2-5-7. Bottleneck = $\min (c(1,2)=7,c(2,5)=5,c(5,7)=10)=5$. Flow = 5.
2. Path: 1-3-6-7. Bottleneck = $\min (c_f(1,3)=10,c_f(3,6)=7,c_f(6,7)=4)=4$. Flow = 5 + 4 = 9.
3. Path: 1-2-4-5-7 (From image page 61). Bottleneck = $\min (c_f(1,2)=2,c_f(2,4)=3,c_f(4,5)=2,c_f(5,7)=5)=2$. Flow = 9 + 2 = 11. (Note: page 61 shows path 1-3-6-7 with bottleneck 4, and 1-2-4-5-7 with bottleneck 2. Earlier path 1-2-5-7 had bottleneck 5)

Check residual graph: No more paths from 1 to 7. Maximum Flow = 11.

b. Consider the following graph to find the minimum connected dominating set showing all the intermediate steps during the constructions. (Solution approach using reduction on pages 49-55)

Graph vertices {1, 2, 3, 4, 5, 6}. Edges (1,2), (1,5), (2,3), (2,5), (3,4), (3,6), (5,6). Greedy approach (Maximize coverage while maintaining connectivity):

1. Calculate N[v]: N[1]={1,2,5}, N[2]={1,2,3,5}, N[3]={2,3,4,6}, N[4]={3,4}, N[5]={1,2,5,6}, N[6]={3,5,6}.
2. Max coverage |N[v]| is 4 (vertices 2, 3, 5). Choose highest ID: 5. $D=\{5\}$. Covered $N[5]=\{1,2,5,6\}$. Uncovered $U=\{3,4\}$.
3. Neighbors of $D=\{5\}$ are $\{1,2,6\}$. Candidates to add:
   • Add 1: Covers none new from $U$.
   • Add 2: Covers {3} from $U$.
   • Add 6: Covers {3} from $U$.
4. Tie between 2 and 6. Choose highest ID: 6. Add 6. $D=\{5,6\}$. Connected (edge 5-6 exists). Covered $N[D]=N[5]\cup N[6]=\{1,2,3,5,6\}$. Uncovered $U=\{4\}$.
5. Neighbors of $D=\{5,6\}$ are $\{1,2,3\}$. Candidates to add:
   • Add 1: Covers none new from $U$.
   • Add 2: Covers none new from $U$.
   • Add 3: Covers {4} from $U$.
6. Choose 3. Add 3. $D=\{5,6,3\}$. Connected (edges 5-6, 6-3 exist). Covered $N[D]=V$.

Minimum Connected Dominating Set: $D=\{3,5,6\}$. Size = 3.