Graph colouring problem

Question

I have the question as stated:

For a graph G with n vertices and 4n edges, Alice claims to have a proper colouring with 3 colours.Bob decides to try to find one by testing each of the possible ways to colour G with 3 colours. Bob can verify if a colouring is proper as soon as he looks at it.

(a) Approximately how many equality operations will it take you to verify or disprove Alice’s claim?

(b) Approximately how many verifications will it take Bob to find a proper colouring with 3 colours, or prove one does not exist?

Here are some aspects where I have difficulties with:

1. I cannot visualize a graph with n vertices and 4n edges looks like, so that I cannot proceed on the colouring by "first fit".
2. Since there is no formula for calculating the chromatic numbers, how can one does so without knowing the structure of the graph?
3. My thought: Can we deal with the bounds of the chromatic number in this case? i.e. from below by finding cliques. Bounding from above is constructive - we give a colouring? If so, how?

Answer 1

In neither section of the problem are you asked to color the graph. In part a you receive Alice's coloring and you are asked to check whether her claim is correct. That means verifying that no edge of the graph connects two like colored vertices. You are asked to imagine a program that implements that and find how many checks are performed. In part b we are just asked how many ways there are to color the vertices with three colors because the verification step is defined to be instant.