#include <stdio.h>

#define N 30		// Maximum number of vertices. Must be <= number of bits in an int variable.
#define OPT 1		// If non-zero, perform optimizations by only checking certain sets of k added edges.

int A[N][N];		// Adjacency matrix of G.
int v[N];		// List of vertices in substructures.
int dg[N];		// Number of cross edges meeting a vertex.
int n1;			// Number of vertices in first subgraph G_1 (if G = G_1\cup G_2 + ke).
int nt;			// Total number of vertices in graph.

// Declare some simple graph types.
//
typedef enum {None=0,Path=1,Cycle=2,Cdag=3,Cplus2=4} gtype;	// Types of graph.
int minsize[]={0,1,3,4,4};					// Minimum number of vertices needed for each type.
char* names[]={"","P_","C_","C^d_","C^+2_"};			// Short names of the types of graph.

// Clear graph and entire adjacency matrix.
// Must be called before addgraph() is used.
//
void cleargraph(){
 int i,j;
 for(i=0;i<N;i++)for(j=0;j<N;j++)A[i][j]=0;			// Zero out adjacency matrix.
 for(i=0;i<N;i++)dg[i]=0;					// Also clear cross-degree array.
 n1=nt=0;							// Graph now has 0 vertices.
}

// Add a vertex disjoint Path or Cycle to current graph.
// Graph (adjacency matrix) should be zeroed first by cleargraph() as addgraph() only adds edges.
// Sequence of calls should be e.g.: cleargraph(); addgraph(t1,v1); addgraph(t2,v2);
//
void addgraph(gtype t,int n){
 int i;
 if(nt+n>N||nt<0){printf("Error: too many vertices in graph\n");exit(0);}
 if(t!=Path&&t!=Cycle){printf("Error: can only construct paths and cycles here\n");exit(0);}
 for(i=nt;i<nt+n-1;i++)A[i][i+1]=A[i+1][i]=1;			// Add path.
 if(t==Cycle)A[nt][nt+n-1]=A[nt+n-1][nt]=1;			// Close cycle.
 n1=nt;nt+=n;							// Update n1,nt.
}

// Recursive routine to find a structure consisting of at most two subgraphs of given form in G.
// v0 = index in v[] of first vertex in current subgraph.
// vn = index in v[] of next vertex in current subgraph.
// bm = bit mask of remaining vertices.
// nr = number of remaining vertices that can be used.
// ch = number of chords found (plus 1 as it counts the closing edge of the cycle as a chord).
// t1,t2 = types of subgraph to find. Current subgraph is type t1.
//
int findr(int v0,int vn,int bm,int nr,int ch,gtype t1,gtype t2){
 int vmax,u,w,c;
 if(v0==vn){							// If subgraph not started.
  if(nr<minsize[t1]+minsize[t2])return 0;			// Fail if too few vertices remaining.
  if(t1==None){t1=t2;t2=None;} 					// Skip trivial graph type.
  if(t1==None)return 1;						// Finished!	
  for(w=0;w<nt;w++){						// Loop over possible first vertices.
   if((bm&(1<<w))!=0){						// Check vertex still available.
    v[v0]=w;							// Record new vertex in v[].
    if(findr(v0,v0+1,bm-(1<<w),nr-1,0,t1,t2))return 1;		// Recursive call to find rest of the structure.
   }
  }
  return 0;							// Failed for all choices of first vertex.
 }
// Check if we have found subgraph and recursively call findr() to find second substructure if done.
 if(vn-v0>=minsize[t1]){					// No point checking if not enough vertices.
  if( (t1==Path)						// We always have constructed a path v[v0]-v[vn-1].
    ||(t1==Cycle && A[v[v0]][v[vn-1]])				// Need a closing edge for cycles.
    ||(t1==Cdag  && A[v[v0]][v[vn-1]] && ch>((vn-v0==4)?1:2))	// Check enough chords for Cdag. Number of chords is ch-1.
    ||(t1==Cplus2&& A[v[v0]][v[vn-1]] && ch>2)){		// Check enough chords for Cplus2. Number of chords is ch-1.
   if(findr(vn,vn,bm,nr,0,t2,None))return 1;			// Recursively find second subgraph.
  }
 }
 if(nr<=minsize[t2])return 0;					// Run out of vertices.
 if(t1!=Path)vmax=v[v0]; else vmax=nt;				// For efficiency, assume first vertex of cycle is largest.
 for(w=0;w<vmax;w++){						// Loop through possible next vertices.
  if((bm&(1<<w))!=0 && A[v[vn-1]][w]){				// Must be available and joined to the previous vertex.
   for(c=ch,u=v0;u<vn-1;u++)c+=A[v[u]][w];			// Count chords.
   v[vn]=w;							// Record new vertex in v[].
   if(findr(v0,vn+1,bm-(1<<w),nr-1,c,t1,t2))return 1;		// Recursive call to find rest of the structure.
  }
 }
 return 0;							// No structure found.
}

// Find number of extra edges needed to ensure no suspended path length >2 in P_* and both ends covered.
// This is used in the optimization of findbetween(). If we have found substructures for all choices of cross edges
// and smaller P_*, then we can assume the cross edges meet the ends of P_* and at least every other vertex along P_*
// as otherwise we would have found a counterexample with smaller P_*.
//
int extraedges(){
 int i,c,f;
 c=f=0;								// c=extra edges needed, f=1 if last vertex covered.
 for(i=n1;i<nt;i++){						// Loop through P_*.
  if(dg[i])f=1;							// If vertex covered, we are OK for this and the next vertex.
  else if(f)f--;						// If last vertex covered, we are still OK.
  else {c++;f=1;}						// Need an extra edge, but then we would be OK for the next vertex.
 }
 return c;
} 

// Optimization check. Returns 0 if current subset of edges does not need to be checks.
// t = Type of graph (either 2 paths or 2 cycles)
// k = Number of remaining edges to be added.
// j = Vertex in G_2 that is incident to last edge added.
//
int optimization(gtype t,int k, int j){
 if(t==Path)return extraedges()<=k;				// For paths, need every other vertex of P_* covered.
 if(t==Cycle && j<nt-1){					// For cycles, require last vertex to have max degree.
// Edges are found in reverse order in the vertex j, so if j<nt-1 the vertex nt-1 already has its final degree
// and vertices <j have zero degree in cross-edges.
  return dg[j]<=dg[nt-1] && (j-n1+1)*dg[nt-1]-dg[j]>=k;		// Degree of j OK and enough room for remaining edges.
 }
 return 1;
} 

// Recursive routine to find structure for all k-sets of edges between G_1 and G_2.
// k = number of remining edges to add.
// l = last edge added (we optimize by assuming edges are chosen in reverse order).
// t1,t2 = structures of subgraph(s) to find.
// nr = max number of vertices these structures can use.
// If f=1 then we make sure the endvertices and at least every other vertex in the path G_2 is covered by cross edges.
// Edges from vertex i<n1 to j>=n1 are sorted by value of i+n1*(j-n1).
// Routine assumes no edges originially exist between G_1 and G_2.
//
int findbetween(int k,int l,gtype t1,gtype t2,int nr,gtype t){
 int e,i,j;
 if(findr(0,0,(1<<nt)-1,nr,0,t1,t2))return 1;			// Substructure exists.
 if(k==0)return findr(0,0,(1<<nt)-1,nr,0,t1,t2);		// No further edges allowed, so fails.
 for(e=k-1;e<l;e++){						// Loop over feasible choices of the next edge.
  i=e%n1; j=e/n1;						// Endvertices of e are i and j+n1.
  A[i][j+n1]=A[j+n1][i]=1;					// Add edge to adjacency matrix. 
  dg[j+n1]++;							// Record the degree of cross-edges to G_2. 
  if(OPT==0||optimization(t,k-1,j+n1)){				// Filter out unnecessary checks if OPT=1
   if(!findbetween(k-1,e,t1,t2,nr,t))return 0;			// Recursively check that it is always OK to include this edge.
  }
  A[i][j+n1]=A[j+n1][i]=0;					// Remove edge from adjacency matrix.
  dg[j+n1]--;							// Return the degree of cross-edges to original value.
 }
 return 1;							// Was always OK.
}

// If k edges are added between two graphs of type t of orders v1 and v2,
// can we always find vertex disjoint graphs of types t1 and t2.
// If s=1 then we must not use all vertices.
//
int between(gtype t,int v1,int v2,int k,gtype t1,gtype t2,int s){
 int i,j;
 printf("%s%d + %s%d + %de",names[t],v1,names[t],v2,k);		// Print the type of graph we are constructing. 
 if(s)printf(" > "); else printf(" >= ");			// Can we use all the vertices?  
 printf("%s*",names[t1]);					// Substructure to find.
 if(t2!=None)printf(" + %s*",names[t2]);
 cleargraph();							// Construct base graph without added edges.
 addgraph(t,v1);
 addgraph(t,v2);
#if OPT
// As an extra optimization, we can always assume one edge goes to last vertex of G_2.
// (For paths: if not, then taking the redundant vertices at the end of the path G_2
// and adding them on at the beginning of G_2 can never hurt us when looking for cyclic substructures.)
// For cycles we can also assume this comes from last vertex of G_1.
// For paths we can only assume this comes from the second half of G_1.
// Note that the largest edge in our ordering can be assumed to be this edge.
 j=n1+v2-1;							// Last vertex of G_2.	
 dg[j]=1;							// Record cross-degree of this vertex.
 if(t==Path)i=v1/2; else i=v1-1;				// Middle or last vertex of G_1.
 for(;i<v1;i++){						// For all choices of largest edge.
  A[i][j]=A[j][i]=1;						// Add edge to adjacency matrix
  if(!findbetween(k-1,i+n1*(j-n1),t1,t2,nt-s,t)){		// Find structure for all choices of remaining k-1 edges
   printf(" No\n");return 0;					// Failed.
  }
  A[i][j]=A[j][i]=0;						// Remove edge from adjacency matrix.
 }
 printf(" Yes\n");return 1;					// Always succeeded.
#else								// Unoptimized version.
 if(findbetween(k,v1*v2,t1,t2,nt-s,t)){				// Find structure for all choices of k edges
  printf(" Yes\n");return 1;					// Always succeeded.
 }
 else {printf(" No\n");return 0;}				// Failed.
#endif
}

// Recursive routine to find substructure for all k-sets of chords within G (assumed to be cycle).
// k = number of remining edges to add.
// l = last edge added (we optimize by assuming edges are chosen in reverse order).
// t1,t2 = structures of subgraph(s) to find.
// nr = max number of vertices these substructures can use.
// Edges from vertex i to j are sorted as nt*j+i, i<j.
// We could add some optimizations on the set of chords added, but the routine is fast enough as it is. 
//
int findwithin(int k,int l,gtype t1,gtype t2,int nr){
 int i,j;
 if(findr(0,0,(1<<nt)-1,nr,0,t1,t2))return 1;			// Substructure exists.
 if(k==0)return 0;						// No further edges allowed, so fails.
 for(j=0;nt*j<l;j++){						// Loop over choices of the next edge.
  for(i=0;i<j&&nt*j+i<l;i++){
   if(!A[i][j]){						// Don't add edge if it already exists.
    A[i][j]=A[j][i]=1;						// Add edge to adjacency matrix.
    if(!findwithin(k-1,nt*j+i,t1,t2,nr))return 0;		// Recursively check that it is always OK to include this edge.
    A[i][j]=A[j][i]=0;						// Remove edge from adjacency matrix.
   }
  }
 }
 return 1;							// Always succeeded.
}

// If k chords are added to a cycle of order v1 can we always find a subgraph of type t1.
// If s=1 then must not use all vertices.
//
int within(int v1,int k,gtype t1,int s){
 printf("C_%d + %de",v1,k);					// Print description of graph.
 if(s)printf(" > "); else printf(" >= ");			// Can we use all the vertices.
 printf("%s*",names[t1]);					// Substructure to find.
 cleargraph();							// Construct base graph without added edges.
 addgraph(Cycle,v1);
 if(findwithin(k,v1*v1,t1,None,nt-s)){				// See if substructure always exists.
  printf(" Yes\n");return 1;					// Always succeeded.
 }
 else {printf(" No\n");return 0;}				// Failed.
}


main(){
 int n,m,k;

 if(sizeof(int)*8<N){printf("Error: maximum size of graph (N) too big\n");exit(0);}
 if(OPT)printf("Optimizations On\n\n"); else printf("Optimizations Off\n\n");

 printf("Lemma 5\n");
 for(n=5;n<=8;n++){
  for(k=2;;k++)if(within(n,k,Cdag,1))break;
  for(;;k++)if(within(n,k,Cplus2,1))break;			// no point looking for C^+2 if no C^\dag
  printf("\n");
 }

 printf("Lemma 9\n");
// Note that wlog P_* has at most 2k-1 vertices. Indeed, if there were a subtended subpath of P_*
// between endvertices of the added edges, we can safely shorten it to length 2 without
// creating any additional C^\dag_*'s. As an extra optimization (if OPT set), we insist that
// the endvertices and every other vertex of P_* meet cross-edges, as otherwise we would find
// a counterexample with smaller size of P_*.
 for(n=1;n<=5;n++){
  for(k=2;;k++)if(between(Path,n,2*k-1,k,Cdag,None,0))break;	// We do the hard case m=2k-1 first.
  for(m=2*k-2;m>=1;m--){
   for(;;k++)if(between(Path,n,m,k,Cdag,None,0))break;		// Then we check the smaller m's.
  }
  printf("P_%d + P_* + %de >= C^d_* OK\n\n",n,k);		// Summary statement of results.

  for(;;k++)if(between(Path,n,2*k-1,k,Cdag,None,1))break;	// no point looking for > if not >=.
  for(m=2*k-2;m>=1;m--){
   for(;;k++)if(between(Path,n,m,k,Cdag,None,1))break;		// Check smaller m's.
  }
  printf("P_%d + P_* + %de > C^d_* OK\n\n",n,k);		// Summary statement of results.
 } 

 printf("Lemma 10\n");

 for(m=3;m<=4;m++){
  for(k=8;;k++)if(between(Cycle,4,m,k,Cycle,Cycle,1))break;
  printf("\n");
 }

 for(n=4;n<=7;n++){
  for(m=3;m<=n;m++)if(m+n>=8){
   for(k=9;;k++)if(between(Cycle,n,m,k,Cdag,Cycle,1))break;
   printf("\n");
  }
 }

// This last section takes a long time to run, especially n=7.

 printf("Lemma 11\n");
 for(n=5;n<=7;n++){
  for(m=4;m<=n;m++){
   for(k=13;;k++)if(between(Cycle,n,m,k,Cdag,Cdag,1))break;
   printf("\n");
  }
 }

 printf("Finished\n");
}