Two observations: If you can find $A$ and $B$ so that their union is all of $G$ and they both induce cliques then you can find $A$ and $B$ that are disjoint cover all of $G$ and also induce cliques.}
Now notice that $A$ and $B$ induce cliques if and only if there are no edges between vertices of $A$ and no edges between vertices of $B$ in the complement of $G$.
So your problem is equivalent to determining if $G^c$ is bipartite, and if it is, finding a partition of $G^c$. This can easily be done in $\mathcal O(n^2)$ time.
Here is some c++11 code:
#include <bits/stdc++.h>
using namespace std;
const int MAX=1010; // maximum number of vertices
set <int> A[MAX];// A[i] stores all the neighbours of vertex i
int C[MAX]; // this store in which "part" we save vertex i
void impossible(){// I just use this to print when I realize its impossible
printf("impossible\n");
exit(0);
}
void dfs(int x){
for(int y:A[x]){
if(C[y]==C[x]) impossible();// this means the graph is not bipartite
if(C[y]==0){
if(C[x]==1) C[y]=2;
else C[y]=1;
dfs(y);
}
}
}
int main(){
int n,m; // number of vertices and edges
scanf("%d %d",&n,&m); // we read n and m
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i!=j) A[i].insert(j); // we want to build the complement, so we start adding every edge
}
}
for(int i=0;i<m;i++){// we read the edges in G and erase them from G^c
int u,v;
scanf("%d %d",&u,&v);
A[u].erase(v);
A[v].erase(u);
}
for(int i=0;i<n;i++){
if(C[i]==0){// if i has not been explored yet we dfs from i
C[i]=1;
dfs(i);
}
}
printf("The set A contains:\n");
for(int i=0;i<n;i++){
if(C[i]==1) printf("%d ",i);
}
printf("\nThe set B contains:\n");
for(int i=0;i<n;i++){
if(C[i]==2) printf("%d ",i);
}
printf("\n");
}
In general, if we take all the vertices of a graph $G$, but only the edges in some matching of $G$, we get a spanning subgraph with maximum degree $1$ (or maybe $0$, if the matching was empty). If the matching was a perfect matching, then the subgraph is $1$-regular.
In our case, the perfect matching $P_1$ gives us a subgraph $G_1$ of $G$ in which every vertex has degree $1$. The prefect matching $P_2$ gives us a subgraph $G_2$ of $G$ in which every vertex has degree $1$ except for $v_1, v_2, v_3, v_4$, which have degree $0$.
In general, if $G_1$ and $G_2$ are the graphs with maximum degree $1$ we got from two matchings in $G$, then it makes sense to look at the symmetric difference $G_1 \mathbin{\Delta} G_2$. (This is the graph which has all the same vertices, and whose edges are the edges present in exactly one of $G_1$ or $G_2$.)
We can't say how many edges $G_1 \mathbin{\Delta} G_2$ has - that depends on how similar the two matchings are. However, every vertex that was covered by both matchings has degree either $0$ or $2$ in $G_1 \mathbin{\Delta} G_2$ (it has degree $0$ if it had the same edge in both matchings, and degree $2$ if the edged were different). Every vertex covered by only one matching has degree $1$ in $G_1 \mathbin{\Delta} G_2$. Finally, every vertex covered by neither matching still has degree $0$.
In our case, $G_1 \mathbin{\Delta} G_2$ has four vertices of degree $1$: $v_1, v_2, v_3, v_4$. Every other vertex has degree $0$ or $2$.
In general, such a symmetric difference is the union of isolated vertices, paths, and cycles. Isolated vertices are the ones which had degree $0$, so we can forget about those. Every other vertex has degree $1$ or $2$. This means that there are some components in which every vertex has degree $2$: those must be cycles. There are also components in which some vertices have degree $1$: those must be paths starting and ending at such a vertex.
In our case, $G_1 \mathbin{\Delta} G_2$ has four vertices of degree $1$: $v_1, v_2, v_3, v_4$. So it contains two paths that start and end at two of these vertices, and everything else is cycles and isolated vertices.
In particular, either one of the path components of $G_1 \mathbin{\Delta} G_2$ gives us the path you're looking for.
Your problem only asks for the path's edges to be contained in $P_1 \cup P_2$. But we can say more: the path must alternate between edges of one matching, and edges of the other. Moreover, its first and last edge must come from $P_1$, because $P_2$ does not cover the endpoints of the path. So the path we find is an augmenting path for the matching $P_2$.
With these augmenting paths, we can do the following:
- Take one of the paths; remove from $P_2$ all of its edges which are in the path, and then add the edges of the path which were not in $P_2$. The result is a matching in $G$ which covers all vertices except for two of $v_1, v_2, v_3, v_4$.
- Do the same for the other path. The result is a perfect matching in $G$ (which may not be the same as $P_1$).
Best Answer
Hint
Your computation will work but it is indeed a bit tedious, and would quickly be not feasible with higher number of nodes. If you want to do something "neat":
Call $G=(V,E)$ your graph, on 8 nodes, 3-regular, hence on 12 edges. Note that your problem is equivalent to
Indeed If you find a perfect matching in $G^c$ (the complement of $G$), then you will have a way to pair all nodes, with no edges (in $G$) between elements of a pair. Now your graph $G^c$ has 8 nodes, and is 4-regular. Do you have notions of perfect matching? and how to prove they exist?
To finish you could