RE: This marriage:
I checked in with the BMD Registry and the marriage record between these two does not list parent's information. So no luck there.
A marriage record for Mary Elizabeth Parker and John William Walters in Sydney (1856) does list a father as Walter Walters but the mother as Elizabeth Holland.
So this may be a bit of a dead end..