Postgres deadlock in INSERT VALUES concurrent with ON DELETE CASCADE
I would not worry about the behavior, just retry the transaction if terminated by the deadlock.

The first transaction tries to delete A and B, and acquires sequentially a lock on them, and the second deletes B and A, with the same approach. Upon locking A and B, none of the two transactions can progress, hence one of them is terminated by a deadlock.