Question 65
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 \gt c$, then $G$ is quasi-colorable."
- 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 \gt c$, then $G$ is quasi-colorable."