Para esse problema é necessário conhecimento sobre DFS.
Note que a mesa é dividida em dois lados, o lado da esquerda e o da direita, ou seja, se eu estou na direita meus amigos estarão na esquerda e vice-versa.
Com isso vamos tentar dividir nosso grafo da seguinte maneira: se eu estou na direita me pinto de 1 e pinto meus amigos de 2 (esquerda), e os amigos dos meus amigos, que não são meus amigos, serão pintados de 1 e assim sucessivamente.
Iremos fazer uma DFS que retorna true se conseguir dividir os amigos e false caso contrário.
Assim nosso algoritmo fica: ao chamar um nó DFS que ainda não foi visitado, coloco ele no lado direito da mesa e percorro sua lista de amigos se o amigos não foi visitado coloco ele do lado esquerdo(2) da mesa e chamo a dfs nele e então percorro sua lista de amigos, só que dessa vez coloco seus amigos do lado direito da mesa e assim sucessivamente, se ele já foi visitado checo estamos do mesmo lado da mesa se sim, retorno false, se não continuo percorrendo a minha lista de amigos, se em nenhum momento da DFS encontrarmos dois amigos do mesmo lado da mesa, retorno true.
Segue código solução para maior entendimento: