show/hide this revision's text 2 Fixed some dim comments.

Isn't this particular case easier to prove using the topology of the independence complexes of your $K_{n,m}$ and $K_{s,t}$?

$Ind(K_{n,m})$ is the disjoint union of an (n-1)-simplex and an (m-1)-simplex, and $Ind(K_{s,t})$ is the disjoint union of a (s-1)-simplex and a (t-1)-simplex. So the Stanley-Reisner complex of the disjoint union of those two graphs would be $\Delta=Ind(K_{n,m}\coprod \Delta=Ind(K_{n,m})\coprod Ind(K_{s,t})$ is the join of those two complexes, which is connected ($\widetilde{H}_0(\Delta)$=0) $\dim\widetilde{H}_0(\Delta)$=0) and has $\widetilde{H}_1(\Delta)=1$.\dim\widetilde{H}_1(\Delta)=1$.

From Hochster's formula, this gives you a nonzero Betti number at homological stage n+m+s+t-2, so $pd(R/I)\geq n+m+s+t-2$. As this is the entire Stanley Reisner complex, and as the complex is connected, that's as high as the projective dimension could be.

This isn't quite the complex you wanted - but you'd just need to examine what happens to the join of the independence complexes of $K_{n,m}$ and $K_{s,t}$ after deleting the face ${v,w}$ corresponding to the edge you added between the graphs and all of the faces containing it. This complex still is connected and has $\dim H_1(\Delta)=1$, \widetilde{H}_1(\Delta)=1$, so the projective dimension of both complexes is the same.

I guess a more general answer to this particular question though is - instead of computing the resolutions using edge ideals, you might consider using GAP to compute the homology of subcomplexes of your total complex of the appropriate size. These homology calculations combined with Hochster's formula are often better tools at proving projective dimension or regularity bounds than trying to resolve the ideals themselves.
show/hide this revision's text 1

Isn't this particular case easier to prove using the topology of the independence complexes of your $K_{n,m}$ and $K_{s,t}$?

$Ind(K_{n,m})$ is the disjoint union of an (n-1)-simplex and an (m-1)-simplex, and $Ind(K_{s,t})$ is the disjoint union of a (s-1)-simplex and a (t-1)-simplex. So the Stanley-Reisner complex of the disjoint union of those two graphs would be $\Delta=Ind(K_{n,m}\coprod Ind(K_{s,t})$ is the join of those two complexes, which is connected ($\widetilde{H}_0(\Delta)$=0) and has $\widetilde{H}_1(\Delta)=1$.

From Hochster's formula, this gives you a nonzero Betti number at homological stage n+m+s+t-2, so $pd(R/I)\geq n+m+s+t-2$. As this is the entire Stanley Reisner complex, and as the complex is connected, that's as high as the projective dimension could be.

This isn't quite the complex you wanted - but you'd just need to examine what happens to the join of the independence complexes of $K_{n,m}$ and $K_{s,t}$ after deleting the face ${v,w}$ corresponding to the edge you added between the graphs and all of the faces containing it. This complex still is connected and has $\dim H_1(\Delta)=1$, so the projective dimension of both complexes is the same.

I guess a more general answer to this particular question though is - instead of computing the resolutions using edge ideals, you might consider using GAP to compute the homology of subcomplexes of your total complex of the appropriate size. These homology calculations combined with Hochster's formula are often better tools at proving projective dimension or regularity bounds than trying to resolve the ideals themselves.