Let's work through each part step by step. --- ## Part (i): Minimum Number of Trails in a Graph with \( k \) Odd Degree Vertices ### **Step 1: Understanding the Problem** - We have a connected graph \( G \) with \( k \) vertices of odd degree (\( k > \)). - We want to cover edges with edge-disjoint trails (no edge repeats in a trail, and trails don't share edges). - **Claim:** The minimum number of such trails is \( \frac{k}{2} \). --- ### **Step 2: Recall Key Graph Theory Concepts** - **Trail:** A walk in which all edges are distinct. - **Euler Trail:** A trail that visits every edge exactly once. - **Euler’s Theorem:** A connected graph has an Euler trail iff it has exactly or 2 vertices of odd degree. --- ### **Step 3: Pairing Odd Degree Vertices** - Every trail that starts and ends at vertices of odd degree "uses up" two odd degree vertices (because entering and leaving a vertex uses up two edges). - Thus, to cover all edges, each trail can start and end at two odd degree vertices. - With \( k \) odd degree vertices, we can pair them up into \( \frac{k}{2} \) pairs. - Each pair can be connected by a trail that covers some edges without repeating. --- ### **Step 4: Why Can't We Do Fewer?** - Each trail can only "use up" two odd degree vertices (at its ends). - Therefore, the absolute minimum number of such trails is \( \frac{k}{2} \). - This is a classic result in graph theory. --- ### **Conclusion for (i):** \[ \boxed{\text{The minimum number of edge-disjoint trails covering all edges of } G \text{ is } \frac{k}{2}.} \] --- ## Part (ii): Pen-Strokes Needed for Figure 2.20 Let's analyze the diagram. ### **Step 1: Model the Graph** - There are three concentric circles, each divided into four segments by four straight lines. - The straight lines connect at the center and radiate outward, intersecting the circles. #### **Vertices and Degrees** - **Vertices:** Intersection points (center, and intersections at each circle). - The degree at each intersection = number of lines meeting at that point. Let's count the **odd degree vertices**. #### **At the Center:** - 4 straight lines meet at the center. **Degree = 4** (even). #### **At Each Circle:** - Each straight line crosses all 3 circles, making 4 intersection points per circle. - At each such intersection, the line (1 edge) and the circular arc (2 arcs meeting at each point) meet, so degree = 3 (odd). - **Number of such vertices:** 4 (lines) × 3 (circles) = **12 vertices of degree 3** (odd). #### **At the Outer Edge:** - Each straight line ends at the outermost circle. Let's assume the outermost intersections are just like other circle intersections, so total odd-degree vertices is still 12. --- ### **Step 2: Apply the Result from (i)** - The minimum number of trails = \( \frac{k}{2} \), where \( k \) is the number of odd-degree vertices. - Here, \( k = 12 \). \[ \text{Number of pen-strokes needed} = \frac{12}{2} = \boxed{6} \] --- ## **Summary of Answers** ### (i) **Minimum number of trails:** \[ \boxed{\frac{k}{2}} \] ### (ii) **Pen-strokes needed to draw Fig. 2.20:** \[ \boxed{6} \] --- If you want a more detailed breakdown of the degrees for each node in the diagram, let me know!