## Mentor Graphics Interview Question

MTSs**Country:**India

**Interview Type:**In-Person

yes. color a K5, a complete graph with 5 vertices using only two colors such that no two neighbors share the same color?

There seems to be some confusion here. The 4-color theorem is about coloring of contiguous regions on a planar map and is not about coloring a vertex graph with arbitrary edges.

Graph coloring is not unsolvable, but NP-complete. However, it seems that this question is asking for a coloring *given* that the graph can be colored with only 2 colors. That is not NP-complete, and can be done with a simple BFS.

I dont know but interviewer asked me to tell first whether this is possible or not.

May be this is related to some well known Graph Theorem.I am all nill in that !

It is about a well-known theorem in graph theory. The theorem is that graph coloring is NP-complete. That doesn't mean it's impossible. It just means, in very rough and oversimplified terms, that no exact algorithms for solving this problem are known that are substantially more efficient than brute-force search. That doesn't even mean such algorithms don't exist, only that none are known right now.

I used the word unsolvable in the sense that not any graph can be colored using 2 colors only and since the question didn't mention that graph is bipartite I assumed the input can have any graph for example a complete graph with 1000 vertices.

0 represents RED & 1 represents GREEN;

c representc color. color[i]==0 indicates ith vertex is colored RED.

```
int colorGraph(G[][],int c,int source,int color[])
{
color[source]=c;
for each V adj to source
{
if(isColored(V)==c)
return 0;
if(colorGraph(G,1-c,V,color)==0) return 0;
}
return 1;
}
```

This is the problem of determining whether a graph is Bipartite or not and can be done using BFS on the graph.

- anujkaliaiitd July 15, 2012