So if I understand correctly, your proof is:
- We must use at least $7$ colors to color $G$, since it has the subgraph $G_2$, which has chromatic number $7$.
- We pick some $7$-coloring of $G_2$.
Using those colors, we color two non-adjacent vertices in $G_1$ the same color. (There must be a non-edge in $G_1$ for $G_1$ to be $5$-colorable.)
- If the two non-adjacent vertices in $G_1$ don't include $7$ or $8$, then we have colored $4$ vertices in $G_1$ with $3$ colors, leaving $4$ vertices to be colored with $4$ remaining colors.
- If the two non-adjacent vertices in $G_1$ include $7$ or $8$, then we have colored $3$ vertices in $G_1$ with $2$ colors, leaving $5$ vertices to be colored with $5$ remaining colors.
Either way, we can easily color the remaining vertices in $G_1$.
- Thus we have a $7$-coloring, and $G$ has chromatic number $7$.
It's long, but it works.
A shorter way is to find colorings of $G_1$ and $G_2$, then modify one of them so that vertices $7$ and $8$ receive the same color in both.
After some more thinking, I found a simple solution. We get it very quickly from two results which are well-known in graph theory, though for completeness I will include their proofs.
Lemma 1. A graph $G$ with minimum degree $k$ contains a cycle of length at least $k+1$.
Proof. Take the longest path $v_0, v_1, v_2, \dots, v_\ell$ in $G$. The vertex $v_0$ has at least $k$ neighbors, and all of them must be other vertices on the path, because otherwise we could extend the path and make it even longer. The last of $v_0$'s neighbors on the path must be at least as far as $v_k$ (since there's $k$ of them), so we get a cycle of length at least $k+1$ by following the path from $v_0$ to $v_0$'s last neighbor, then taking the edge back to $v_0$.
Conversely, if the longest cycle in a graph $G$ has length $k$, then it has a vertex of degree $k-1$ or less. What's more, in every subgraph $H$ of $G$, the longest cycle has length $k$ or less (if it's a cycle in $H$, it's a cycle in $G$, too). So $H$ must have a vertex of degree $k-1$ or less.
A graph with this property - every subgraph has a vertex of degree $k-1$ or less - is called $(k-1)$-degenerate.
Lemma 2. A $(k-1)$-degenerate graph $G$ has chromatic number at most $k$.
Proof. We induct on the number of vertices in $G$. When $G$ has $k$ vertices or fewer, we can $k$-color $G$ by giving all the vertices different colors.
Otherwise, let $v$ be a vertex of degree $k-1$ or less. $G-v$ is also $(k-1)$-degenerate (every subgraph of $G-v$ is a subgraph of $G$) and has one fewer vertex, so by induction $G-v$ is $k$-colorable. We can $k$-color $G$ by starting with the $k$-coloring of $G-v$, then giving $v$ a color distinct from the colors on its neighbors (which eliminates at most $k-1$ options).
Putting together the two lemmas: a graph with circumference $k$ is $(k-1)$-degenerate, so it has chromatic number at most $k$. The chromatic number is at most the circumference.
Best Answer
1) What I heard is that, it is conjectured that the problem of determining a graph is 3-colorable or not does not have a polynomial time algorithm.
2) Brooks' theorem states that any graph that is neither complete nor an odd cycle satisfies: $$\chi(G)\leq \triangle(G)$$ Thus, Brooks' theorem can be used to deduce that the Petersen graph is 3-colorable.