One can enter into a relationship with what plausibly seems to be a hallucination or imaginary friend, yet is actually not a hallucination.1 This is relevant because in such a case, one does not have a belief that another person exists.
You could form a relationship with someone while being unsure of whether they are conscious, while they in fact are conscious.1 This is relevant because if you could form a relationship with someone like that, then you can form a relationship with someone while not knowing whether they exist.
One can enter into a relationship with what plausibly seems to be an A.I. or simulated person, one which actually is a real person.1 This is relevant because in such a case, one does not have a belief that another person exists.
Prisoners in solitary confinement making tapping noises to each other can be in a relationship, while not being sure whether the other exists.1
One can enter into relationship with an unknown benefactor.1 This is relevant because the relationship with a person does not require belief that a know person gave you the gift.