Let's tackle each part step by step, as requested, with explanations after each step and the final answer at the end: --- ### (a) Show that \(\frac{|V(G)|}{4} \leq a(G) \leq \frac{|V(G)|}{2}\), where \(a(G)\) is the size of a maximum independent set in a 3-regular graph. #### Step 1: Prove \(a(G) \leq \frac{|V(G)|}{2}\). **Explanation:** In any graph, the maximum size of an independent set is at most half the vertices if the graph is regular of odd degree. Suppose \(S\) is a maximum independent set. Each vertex in \(S\) has 3 neighbors, none of which are in \(S\). Therefore, \(S\) and its neighbors together account for at least \(4|S|\) vertices, but since the graph is only 3-regular, we need to be more careful. But if \(S\) is more than \(|V(G)|/2\), then its complement has less than \(|V(G)|/2\) vertices, so at least one vertex in \(S\) would have all neighbors inside \(S\), contradicting independence. Thus, \(a(G) \leq \frac{|V(G)|}{2}\). --- #### Step 2: Prove \(a(G) \geq \frac{|V(G)|}{4}\). **Explanation:** Turán's theorem (or, more simply, the greedy algorithm) tells us that a \(d\)-regular graph (here \(d=3\)) has an independent set of size at least \(\frac{|V|}{d+1}\). So, \(a(G) \geq \frac{|V|}{4}\). --- **Final Answer (a):** \[ \boxed{ \frac{|V(G)|}{4} \leq a(G) \leq \frac{|V(G)|}{2} } \] --- ### (b) Show that \(\frac{|V(G)|}{2} \leq \beta(G) \leq \frac{3|V(G)|}{4}\), where \(\beta(G)\) is the size of a minimum vertex cover. #### Step 1: Prove \(\beta(G) \geq \frac{|V(G)|}{2}\). **Explanation:** In any graph, the complement of an independent set is a vertex cover. From part (a), the largest independent set is at most \(\frac{|V(G)|}{2}\). So, the smallest vertex cover is at least \(\frac{|V(G)|}{2}\). --- #### Step 2: Prove \(\beta(G) \leq \frac{3|V(G)|}{4}\). **Explanation:** From part (a), there exists an independent set of size at least \(\frac{|V(G)|}{4}\). The complement is a vertex cover of size at most \(|V(G)| - \frac{|V(G)|}{4} = \frac{3|V(G)|}{4}\). --- **Final Answer (b):** \[ \boxed{ \frac{|V(G)|}{2} \leq \beta(G) \leq \frac{3|V(G)|}{4} } \] --- ### (c) Find a 3-regular graph \(G\) such that \(a(G) = \frac{|V(G)|}{4}\). #### Step 1: Consider the 3-dimensional cube \(Q_3\). **Explanation:** \(Q_3\) has 8 vertices, each of degree 3. The largest independent set in \(Q_3\) is of size 2. But let's check: Actually, in \(Q_3\), the largest independent set is 4 (every even-weight binary string), so that's not \(\frac{8}{4}=2\). Try \(K_{4,4}\) minus a perfect matching (the cubic bipartite graph known as the "cubic cage" or the "octahedron graph"). But in \(K_{4,4}\) minus a perfect matching, maximum independent set is 4. In fact, the minimal possible value, i.e., \(\frac{|V|}{4}\), is achieved for certain graphs called the Petersen graph. #### Step 2: Petersen graph. **Explanation:** The Petersen graph is 3-regular, has 10 vertices, but its largest independent set is 4. So, \(a(G) = 4\), and \(\frac{|V|}{4} = \frac{10}{4} = 2.5\), but the answer must be integer. But by construction, the tightness is for graphs with high edge density and minimal independence. Let’s check the 3-regular graph on 4 vertices — but that's \(K_4\): each vertex is connected to all others, but that's 3-regular, and the largest independent set is 1, and \(4/4=1\). So, for \(K_4\): \(a(G) = 1 = 4/4\). --- **Final Answer (c):** \[ \boxed{ K_4 \text{ (the complete graph on 4 vertices) is 3-regular, and its largest independent set is 1, so } a(G) = \frac{|V(G)|}{4}. } \] --- ### (d) Find a 3-regular graph \(G\) such that \(a(G) = \frac{|V(G)|}{2}\). #### Step 1: Consider the 3-dimensional cube \(Q_3\) again. **Explanation:** As above, \(Q_3\) has 8 vertices, and as a bipartite graph, its maximum independent set is 4. \(\frac{8}{2} = 4\), so it matches. #### Step 2: Check for other examples. **Explanation:** Any 3-regular bipartite graph with \(2n\) vertices will have an independent set of size \(n = \frac{|V|}{2}\). --- **Final Answer (d):** \[ \boxed{ Q_3 \text{ (the 3-dimensional cube) is 3-regular, and } a(G) = \frac{|V(G)|}{2}. } \] Or, in general, **any 3-regular bipartite graph** (e.g., the cube graph \(Q_3\)).

**(a)** \(\displaystyle \frac{|V(G)|}{4} \leq a(G) \leq \frac{|V(G)|}{2}\) *Explanation:* In a 3-regular graph, the largest independent set \(a(G)\) cannot exceed half the vertices because, in the extreme case, selecting more than half would force neighboring vertices to be in the set (violating independence). Conversely, by greedy algorithms or Turán’s theorem, we can always find an independent set of size at least \(\frac{|V|}{4}\). --- **(b)** \(\displaystyle \frac{|V(G)|}{2} \leq \beta(G) \leq \frac{3|V(G)|}{4}\) *Explanation:* The minimum vertex cover \(\beta(G)\) is at least the size of the complement of the maximum independent set, which is at least \(\frac{|V|}{2}\). The upper bound follows because, from the maximum independent set size, the remaining vertices form a vertex cover with size at most \(\frac{3|V|}{4}\). --- **(c)** A 3-regular graph \(G\) with \(a(G) = \frac{|V(G)|}{4}\): *Example:* The complete graph on 4 vertices, \(K_4\), is 3-regular. Its maximum independent set has size 1, and since \(|V|=4\), \[ a(G) = 1 = \frac{4}{4}. \] --- **(d)** A 3-regular graph \(G\) with \(a(G) = \frac{|V(G)|}{2}\): *Example:* The 3-dimensional cube graph \(Q_3\) has 8 vertices, each degree 3, and its maximum independent set has size 4, which equals \(\frac{8}{2}\). Thus, \(Q_3\) satisfies the condition.

**(a)** \(\displaystyle \frac{|V(G)|}{4} \leq a(G) \leq \frac{|V(G)|}{2}\) *Explanation:* In a 3-regular graph, the maximum independent set size \(a(G)\) cannot exceed half the vertices because selecting more than half would force neighboring vertices to be included, violating independence. Conversely, by greedy algorithms or Turán’s theorem, we can always find an independent set of size at least \(\frac{|V|}{4}\). --- **(b)** \(\displaystyle \frac{|V(G)|}{2} \leq \beta(G) \leq \frac{3|V(G)|}{4}\) *Explanation:* The minimum vertex cover \(\beta(G)\) is at least the size of the complement of the maximum independent set, which is at least \(\frac{|V|}{2}\). The upper bound follows because, from the maximum independent set size, the remaining vertices form a vertex cover with size at most \(\frac{3|V|}{4}\). --- **(c)** A 3-regular graph \(G\) with \(a(G) = \frac{|V(G)|}{4}\): *Example:* The complete graph on 4 vertices, \(K_4\), is 3-regular. Its maximum independent set has size 1, and since \(|V|=4\), \[ a(G) = 1 = \frac{4}{4}. \] --- **(d)** A 3-regular graph \(G\) with \(a(G) = \frac{|V(G)|}{2}\): *Example:* The 3-dimensional cube graph \(Q_3\) has 8 vertices, each degree 3, and its maximum independent set has size 4, which equals \(\frac{8}{2}\). Thus, \(Q_3\) satisfies the condition.