In this time of mass staying-at-home, jigsaw-puzzles seem to have become rather popular. Same in my household...and this made me wonder: the "standard" 1000(-ish)-piece puzzle is 27 by 38 pieces. Assuming the pieces are all interlocking (e.g., standard male/female puzzle shape combinations), I was wondering ¿what is the maximum number of pieces that can be omitted from the puzzle while every remaining pieces would be connected to every other piece by an interlocked pathway?
Of course, the next question would be: ¿what about an $r \times c$ sized puzzle?
Update #1
The image in my mind was a nearly complete puzzle with pieces missing. So,
let's assume the entire border must be present. Let's also assume there must be at least one piece not directly connected to the edge.
I'm also thinking there needs to be another assumption to make it so that there are "holes" visible in the puzzle (and not just an empty puzzle...e.g., 1 puzzle piece does not a puzzle make). So, I'm thinking an additional criterion needs to be something like: any missing section must consist of $m$ or fewer pieces.