Demo:

There are three questions:

1. How many subgraphs whose Num(vertices) <= 5 and all vertices have two degrees?




2. How many subgraphs whose Num(vertices) == 4 and all vertices have 3 degrees?




3. If two more edges are added, maximum of the number of subgraphs who has 4 vertices and all vertices' degrees are 3. (For the demo above, $binom25$, so 10 cases available: 5, 3, 3, 3, 3, 2, 2, 2, 2, 5 is the maximum.

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

const int ADD = 1;
const int DELETE = 0;

using std::vector;
using std::cout;
using std::transform;
using std::make_move_iterator;
using std::begin;
using std::max_element;
using std::initializer_list;
using std::end;
using std::find;
using std::move;
using std::back_inserter;

using v1d = vector<int>;
using v2d = vector<vector<int>>;
using v3d = vector<vector<vector<int>>>;

template class vector<int>; // useful for debugger
template class vector<vector<int>>;
template class vector<vector<vector<int>>>;

v2d graph;

void testVertice(const v1d& vertice);
void testSubsets(const v3d& subsets);
void testSubset(const v2d& subsets);

int countDegree(const v2d& v2)

 int degree = 0;
 for (const auto& x : v2)
 degree += count(begin(x) + 1, end(x), 1);
 return degree;


void buildGraph()

 graph =
 
 1, 0, 1, 1, 0, 0, 0,
 2, 1, 0, 1, 1, 1, 0,
 3, 1, 1, 0, 1, 1, 0,
 4, 0, 1, 1, 0, 1, 1,
 5, 0, 1, 1, 1, 0, 1,
 6, 0, 0, 0, 1, 1, 0
 ;


template<typename T, typename TPP>
void generateSubsets(int i, int l, int r, T& temp, TPP& ans, const T& graph_) // make subsets, rather than subgraphs

 if (i == graph_.size())
 
 if (temp.size() >= l && temp.size() < r)
 ans.push_back(temp);
 return;
 

 generateSubsets(i+1, l, r, temp, ans, graph_);
 temp.push_back(graph_[i]);
 generateSubsets(i+1, l, r, temp, ans, graph_);
 temp.pop_back();




void repairSubsets(v3d& ans) //remove redundent degrees in graphs.

 for(v2d& subset : ans)
 
 v1d points;

 transform(begin(subset), end(subset), back_inserter(points),
 (const v1d& v) return v.front(); );

 for(v1d& vertice : subset)
 for_each(begin(vertice) + 1, end(vertice),
 [&points, &vertice, index = 1](int& x) mutable
 
 if (x == 1 && find(begin(points), end(points), index) == end(points))
 vertice[index] = 0;
 index++;
 );
 


v3d modifyEdge(int l, int r, const v2d& graph_, int OP) // Add or remove edges

 v1d points;
 v2d pairs, temp;
 v3d ans, subsets;
 int degree = countDegree(graph_);
 auto tot = graph_.size() * (graph_.size() - 1);

 if(OP == 0) // delete edges
 2 * l > degree)
 return ;
 if (2 * r > degree)
 r = degree / 2 + 1;
 
 else // add edges
 
 if (2 * l + degree > tot)
 return ;
 if (2 * (r - 1) + degree > tot)
 r = (tot - degree) / 2 + 1;
 

 OP = OP == 0 ? 1 : 0; // reverse OP

 transform(begin(graph_), end(graph_), back_inserter(points),
 (const v1d& v) return v.front(); );

 for (auto i = 0; i < graph_.size(); i++)
 
 for (auto j = 1; j < graph_[i].size(); j++)
 
 if (
 graph_[i][j] == OP &&
 j != graph_[i][0] &&
 find(begin(points), end(points), j) != end(points)
 )
 
 if (graph_[i][0] < j)
 
 pairs.emplace_back(initializer_list<int>i, j);
 
 else
 
 auto index_ =
 find_if(begin(pairs), end(pairs),
 [&](v1d pair)
 
 return graph_[pair[0]][0] == j && pair[1] == graph_[i][0];
 )
 - begin(pairs);

 auto& temp = pairs[index_];
 temp.push_back(i);
 temp.push_back(j);
 
 
 
 

 generateSubsets(0, l, r, temp, subsets, pairs);

 OP = OP == 0 ? 1 : 0;

 transform(begin(subsets), end(subsets), back_inserter(ans),
 [&graph_, OP](v2d subset)
 v2d temp = graph_;
 for_each(begin(subset), end(subset),
 [&temp, OP](v1d pair)
 
 temp[pair[0]][pair[1]] = OP;
 temp[pair[2]][pair[3]] = OP;
 );
 return temp;
 
 );

 return ans;





v3d makeSubGraphs(v3d&& subsets)

 v3d subGraphs;

 for_each(begin(subsets), end(subsets),
 [&](v2d& subset)
 
 if (subset.size() != 0)
 
 auto temp = modifyEdge(0, 1e5, subset, DELETE);
 subGraphs.insert(end(subGraphs), begin(temp), end(temp));
 
 );

 return subGraphs;


v3d addEdges(v3d&& subsets, int n)

 v3d subGraphs;

 for_each(begin(subsets), end(subsets),
 [&](v2d& subset)
 
 if (!subset.empty())
 
 auto degree = countDegree(subset);
 auto tot = (subset.size() - 1) * (subset.size());
 int n_ = (tot - degree) / 2 >= n ? n : (tot-degree) / 2;
 auto temp = modifyEdge(n_, n_ + 1, subset, ADD);

 subGraphs.insert(end(subGraphs), begin(temp), end(temp));
 
 );

 return subGraphs;


void testVertice(const v1d& vertice)

 for (auto x : vertice)
 cout << x << " ";
 cout << "n";


void testSubsets(const v3d& subsets)

 for (auto x : subsets)
 
 for (auto y : x)
 
 for (auto z : y)
 
 cout << z << " ";
 
 cout << "n";
 
 cout << "n";
 


void testSubset(const v2d& subset)

 for (auto x : subset)
 
 for (auto y : x)
 
 cout << y << " ";
 
 cout << "n";
 
 cout << "n";


int main()

 buildGraph();
 v3d subsets_Q1, subsets_Q2, subsets_Q3_AC, subsets_Q3_WA;
 v2d temp_Q1, temp_Q2, temp_Q3_AC, temp_Q3_WA;


 testSubsets(subsets_Q3_AC);
 generateSubsets(0, 1, 6, temp_Q1, subsets_Q1, graph);
 generateSubsets(0, 4, 5, temp_Q2, subsets_Q2, graph);
 generateSubsets(0, 4, 5, temp_Q3_WA, subsets_Q3_WA, graph);
 repairSubsets(subsets_Q1);
 repairSubsets(subsets_Q2);
 repairSubsets(subsets_Q3_WA);

 auto subGraphs_Q1 = makeSubGraphs(move(subsets_Q1));
 auto subGraphs_Q2 = makeSubGraphs(move(subsets_Q2));
 auto modifiedSubsets_Q3_WA = addEdges(move(subsets_Q3_WA), 2);
 auto subGraphs_Q3_WA = makeSubGraphs(move(modifiedSubsets_Q3_WA));
 auto countGraphs =
 (int n)
 
 return
 [&, n](v3d& subGraphs)
 
 return
 count_if(begin(subGraphs), end(subGraphs),
 [&](v2d& subGraph)
 
 return
 find_if_not(begin(subGraph), end(subGraph),
 [&](v1d& vertice)
 
 return
 count(begin(vertice) + 1, end(vertice), 1) == n;
 )
 ==
 end(subGraph);
 );
 ;
 ;

 /**************** Q3 *******************/
 subsets_Q3_AC = modifyEdge(2, 3, graph, ADD);
 v1d choices_Q3_AC;
 transform(begin(subsets_Q3_AC), end(subsets_Q3_AC), back_inserter(choices_Q3_AC),
 [&](v2d graph_)
 
 v2d temp_;
 v3d subsets_;
 generateSubsets(0, 1, 5, temp_, subsets_, graph_);
 repairSubsets(subsets_);
 auto subGraphs = makeSubGraphs(move(subsets_));
 return countGraphs(3)(subGraphs);
 );
 /*************************************/

 auto ans_Q1 = countGraphs(2)(subGraphs_Q1);
 auto ans_Q2 = countGraphs(3)(subGraphs_Q2);
 auto ans_Q3_WA = countGraphs(3)(subGraphs_Q3_WA);
 cout << "solution to Q1: " << ans_Q1 << "n";
 cout << "solution to Q2: " << ans_Q2 << "n";
 cout << "solution to Q3(all cases && WA): " << ans_Q3_WA << "n";
 cout << "solution to Q3(maximum && AC): " << *max_element(begin(choices_Q3_AC), end(choices_Q3_AC));
 return 0;

Output:

• Solution to Q1: 17


• Solution to Q2: 1


• Solution to Q3 (all cases and WA): 9


• Solution to Q3 (maximum and AC): 5

Code available here