The square lattice with central forces between nearest neighbors is isostatic with a subextensive number of floppy modes. It can be made rigid by the random addition of next-nearest-neighbor bonds. This constitutes a rigidity percolation transition which we study analytically by mapping it to a connectivity problem of two-colored random graphs. We derive an exact recurrence equation for the probability of having a rigid percolating cluster and solve it in the infinite volume limit. From this solution we obtain the rigidity threshold as a function of system size, and find that, in the thermodynamic limit, there is a mixed first-order–second-order rigidity percolation transition at the isostatic point.