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 oct 2019:  I am very proud that this ALU design was used in the RR6 6-bit Reed Relay computer !

[EDIT. An even simpler relay ALU (3 SPDT relays) was designed and presented HERE ]