4. [10] Call a simple graph $G$ quasi-colorable if we can color each edge blue, red, green, and white such that
- for each vertex $v$ of degree 3 in $G$, the three edges containing $v$ as an endpoint are either colored blue, red, and green, or all three edges are white,
- not all edges are white.
A connected graph $G$ has $a$ vertices of degree $4, b$ vertices of degree 3, and no other vertices, where $a$ and $b$ are positive integers. Find the smallest real number $c$ so that the following statement is true: "If $a / b>c$, then $G$ is quasi-colorable."
Answer:
$1 / 4$
Solution 1: Consider a graph $G$ such that $\frac{a}{b}>\frac{1}{4}$. Note that the number of edges is $\frac{4 a+3 b}{2}$. Additionally, if any two vertices of degree 4 are adjacent, we can simply color that edge red and every other edge in $G$ white to get a valid quasi-coloring. Thus, suppose no two vertices of degree 4 are adjacent. Then, consider the subgraph $G^{\prime}$ resulting from removing all vertices of degree 4. Note that $G^{\prime}$ has $\frac{4 a+3 b}{2}-4 a=\frac{3 b-4 a}{2}c$.
Solution 2: Consider a graph $G$ such that $\frac{a}{b}>\frac{1}{4} \Longleftrightarrow b<4 a$. Note that the number of edges is $\frac{4 a+3 b}{2}$. For each edge $e$ in the graph, create a variable $x_{e}$ in $\mathbb{F}_{7}$. Then, for each vertex $v$ of degree 3 , if the edges incident with $v$ are $e_{1}, e_{2}$, and $e_{3}$, then consider polynomial
$$
P_{v}=x_{e_{1}}^{2}+x_{e_{2}}^{2}+x_{e_{3}}^{2}
$$
in $\mathbb{F}_{7}$. There are $b$ such polynomials, each with total degree 2 . Thus, the since $b<4 a$, we know that the sum of the total degrees over all polynomials, $2 b$, is less than the total number of variables, $\frac{4 a+3 b}{2}$. By Chevalley's Theorem, it follows that there exists a nontrivial solution to the system $P_{v} \equiv 0(\bmod 7)$ for all vertices $v$ of degree 3. Consider one such solution. For each edge $e$, if $x_{e} \equiv 0(\bmod 7)$, then color edge $e$ white. If $x_{e}^{2} \equiv 1(\bmod 7)$, color edge $e$ blue. If $x_{e}^{2} \equiv 2(\bmod 7)$, color edge $e$ red. If $x_{e}^{2} \equiv 4$ $(\bmod 7)$, color edge $e$ green. It is not hard to see that this is a valid quasi-coloring.
To show that $c=\frac{1}{4}$ is indeed the smallest possible solution, we can use the graph shown in the previous solution.