Consider directed graphs where all nodes have 2 inputs and 2 outputs. If we design a box with N inputs and N outputs, what is the smallest number of nodes it must contain to satisfy “pair symmetry” (i.e., each input is paired with some output, but relabeling the N pairs does not change the graph). Please specify the corresponding minimal graph solutions for N=3 and N=4.

Here are two graph examples to help show what I'm looking for: