I Finding the dependence of maximum vertex degree on k-colorability

[Superyoshiom]

How do we describe a construction of a 2-colorable graph where the degree of every vertex is greater than or equal to (|V|-1)/2? Based on that, what can be said about the dependence of maximum vertex-degree on k-colorability of a graph?

My first thought is that in order for a vertex to connect to every single other vertex on a graph, it's degree would have to be |V|-1. But since we're looking at half of that in (|V|-1)/2, it would only be connected to half the vertices in the graph, so if this was the case for all vertices in G we'd be constructing a 2-colorable bipartite graph (is my thought).

I'm not too sure how to deal with the second part, however. I know that in a graph there can be n different colors for k given n vertices in a row and we need to add colors whenever there are adjacent vertices, but I can't figure out how the maximum vertex-degree in particular effects how many colors we can use for a graph.

 

[haruspex]

we'd be constructing a 2-colorable bipartite graph

Right, but you can be a bit more precise. Since it is 2-colorable, it is bipartite. What are the possibilities for the numbers in each part? Does it need to be complete?

Based on that, what can be said about the dependence of maximum vertex-degree

The question seems garbled. The first part concerned the minimum vertex degree, (n-1)/2, not the maximum.
As for the first part, you can cluster the vertices according to colour, with each vertex only allowed to connect into other clusters. But if you make one cluster consist of a single vertex then it can have degree n-1, so it doesn’t say anything about the max vertex degree. I would interpret it as asking how high the minimum vertex degree can be.