dp[赤の個数][緑の個数][青の個数][行った頂点] := 可否
      

というビット DP.
二頂点を選ぶとそこを結ぶ辺が決まるので、その色を見る。
二頂点の組み合わせは毎回全部試すことになるので、今いる頂点を覚える巡回セールスマン的なアレは不要。

#include <iostream>
#include <algorithm>
using namespace std;

class RGBTree { public: string exist(vector<string> G); };

string RGBTree::
exist(vector<string> G) {
  int n = G.size();
  int x = n / 3;
  // dp[赤の個数][緑の個数][青の個数][行った頂点] := 可否
  vector<vector<vector<vector<bool>>>> dp(x+1, vector<vector<vector<bool>>>(x+1, vector<vector<bool>>(x+1, vector<bool>(1<<n, false))));
  dp[0][0][0][0] = true;
  for(int rcnt=0; rcnt<=x; ++rcnt) { // x を含めるのを忘れないように
    for(int gcnt=0; gcnt<=x; ++gcnt) {
      for(int bcnt=0; bcnt<=x; ++bcnt) {
        for(int mask=0; mask<1<<n; ++mask) {
          if(!dp[rcnt][gcnt][bcnt][mask]) { continue; }
          for(int i=0; i<n; ++i) {
            for(int j=i+1; j<n; ++j) { // 頂点 i と j を結ぶ辺
              if(G[i][j] == '.') { continue; }
              if((mask >> i & 1) && (mask >> j & 1)) { continue; } // 両頂点に訪問済みならば、そこを結ぶ辺はもう見た。
              int nrcnt = rcnt + (G[i][j] == 'R'),
                  ngcnt = gcnt + (G[i][j] == 'G'),
                  nbcnt = bcnt + (G[i][j] == 'B');
              if(nrcnt > x) { continue; }
              if(ngcnt > x) { continue; }
              if(nbcnt > x) { continue; }
              int nmask = mask | (1<<i) | (1<<j);
              dp[nrcnt][ngcnt][nbcnt][nmask] = true;
            }
          }
        }
      }
    }
  }
  bool able = dp[x][x][x][(1<<n)-1];
  return able ? "Exist" : "Does not exist";
}
      

(ΦωΦ)＜つづく