- 29

- 0

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.