Nmat answer is correct the absolute minimum you would need to rebuild a wallet is the private key of the address.
An alternative is a deterministic wallet.
What is a deterministic wallet?
A deterministic wallet can use cryptographic algorithms to create (and recreate) and wallet containing multiple public/private keys from a single passphrase.
A deterministic wallet has the advantage of being able to create an infinite number of addresses from a single passphrase.
A deterministic wallet has the disadvantage that if the passphrase is retained but the software & algorithm is lost then the addresses can never be recreated and all value lost.
That risk could be partially mitigated by keeping multiple copies of the wallet generation software both online and offline. As a final backup the algorithm (and optionally the passphrase) could be etched or cut into a thin sheet of aluminum (8.5" x 11" to simplify storage) using a laser cutter. This would provide a time resistant disaster recovery method. Using a sheet with dimensions of standard documents would allow it to be easily stored in a safe or safety deposit box. This task is simplified because many cryptographic algorithms can be expressed using diagrams which reduces the amount of space necessary to express the algorithm.
For example SHA-256 (and SHA-512) can be partially expressed by this diagram:
To completely express the algorithm you also need to record each variable, the number of rounds, and the meaning of the symbol operators.