On the pages of Dieter Mueller you can find a nice Relay ALU with 5 relays. However, this can be improved to the following:
Only 4 relays are used now. The improvement is based on drawing 2 of the carrry generation of the Fast carry circuit described in another log. If you do not want to use diodes, you can instead use a relay contact to disable the carry. Using relays with two contacts, a single relay can disable the carry for two bits.
[EDIT. An even simpler relay ALU (3 SPDT relays) was designed and presented HERE ]