Let there be $G = (V,E_1\cup E_2)$ such that $(V,E_1)$ is a planar graph without triangles, and $(V,E_2)$ is without circles, show that $G$ is $6$-colorable

Can I prove here that $E_1$ and $E_2$ has at least one edge that is inside both of them when the vertices are $v_1,v_2,v_3,\dots,v_n$, I couldn't find why this is wrong, can someone please show it using the pigeon hole principle.

  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Pedro
    Aug 5, 2022 at 9:12


You must log in to answer this question.

Browse other questions tagged .