To prove the existence of a graph $G$ with 5 nodes such that both $G$ and $\overline{G}$ (the complement of $G$) have chromatic number $\chi \geq 3$, we construct such a graph and verify its properties.

---

Step 1: Define chromatic number

The chromatic number $\chi(G)$ of a graph $G$ is the smallest number of colors needed to color its vertices such that no two adjacent vertices share the same color.

---

Step 2: Construction of $G$

We will construct $G$ such that:

• $G$ is a graph on 5 vertices.
• $G$ is not bipartite (i.e., $\chi(G) \geq 3$).
• The complement $\overline{G}$ also has $\chi(\overline{G}) \geq 3$.

An example of such a graph $G$ is the cycle graph $C_5$ (a cycle on 5 vertices). This graph is defined as follows:

• $V(G) = \{v_1, v_2, v_3, v_4, v_5\}$,
• $E(G) = \{(v_1, v_2), (v_2, v_3), (v_3, v_4), (v_4, v_5), (v_5, v_1)\}$.

---

Step 3: Verify properties of $G$

1. Chromatic number of $G$:

   • The cycle graph $C_5$ is known to be a non-bipartite odd cycle.
   • Hence, $\chi(C_5) = 3$, since we need three colors to color the graph.

2. Complement $\overline{G}$:

   • In the complement $\overline{G}$, edges exist between vertices that are not adjacent in $G$.
   • $\overline{C_5}$ forms a complete graph $K_2$ plus an isolated triangle $K_3$.
   • The chromatic number of $\overline{G}$ is determined by its largest clique (here the triangle $K_3$), so $\chi(\overline{G}) = 3$.

---

Step 4: Conclusion

Both $G$ and $\overline{G}$ satisfy $\chi \geq 3$. Thus, the cycle graph $C_5$ is an example of a graph with the desired properties.

---

Would you like a detailed diagram of $G$ and $\overline{G}$ or further elaboration? Let me know!

Here are 5 follow-up questions to consider:

1. What is the chromatic number of other cycle graphs $C_n$ for $n \geq 3$?
2. How do the properties of $\chi(G)$ and $\chi(\overline{G})$ relate to the clique number of these graphs?
3. Can we generalize this result to other numbers of nodes?
4. How does the chromatic number relate to planarity of graphs?
5. Can we extend this problem to weighted or directed graphs?

Tip: For constructing graph complements, remember that $\overline{G}$ includes all edges not present in $G$, but no self-loops.