[Math] 2-colorable belongs to $\mathsf P$

Question

To show that 2-colorable belongs to $\mathsf P$, I have a straightforward mental description in mind that I don't think will be considered as a formal proof. Hence I am interested to know how this must be said as an answer to this question. Here's what I think: Say we have 2 colors and n vertices. 2-coloring will be applied such that no two adjacent vertices have the same color. If a vertex is in color A, the other is B and so on. Is my reasoning correct?

Appendix: A graph G is said to be k-colourable if and only if a k-colouring of G exists.

A k-colouring is an assignment of k colours to the vertices of a graph G such that no edge joins two vertices of the same colour.

Answer 1

You have the idea, but "the other" what? One should present a more explicit algorithm and then investigate if it is polynomial. So, to elaborate your idea

1. Prepare an empty queue $Q$ and assign colour $0$ to each vertex.
2. If $Q$ is empty go to step 7; otherwise pop $(v,c)$ from $Q$
3. If the current colour of $v$ is $c$, go to step 2; if it is $-c$, the algorithm terminates: No 2-colouring exists
4. Assign colour $c$ to vertex $v$
5. Enumerate all neighbours of $v$ (that is all edges $vw$ with one end $v$). For each neighbour $w$ of $v$, push $(w,-c)$ to $Q$
6. Go to step 2.
7. Select any vertex $x$ that has not been coloured yet. If no such $x$ exists the algorithm terminates and the graph is 2-coloured.
8. push $(x,+1)$ to the queue $Q$ and go to step 2.

Considering memory, a little refinement of the above can get along with one bit plus one pointer per vertex to realize the queue. Can you determine the time complexity of the algorithm?