Yes, they must be in the same haplogroup to be related within a genealogical time frame. The common ancestor for members lived thousands of year ago. Matching does not offer much proof, but mismatching is definitive. However, there is also the possibility of another non-paternal event in each lineage, so you would want to test several people.
See 23-27 on this page for guidelines on interpreting results:
You would hope for at least a 65/67 or 109/111 match in these circumstances, but there can be wide variations even in close cousins. Distant cousins can be closer matches than close cousins.
If there are any mismatches, you can test other lines to see if any recent mutations can be bypassed. In particular, you would want to test descendants of other sons of Albert to deduce his haplotype. You need to test descendants of different sons until you get matches on all markers. See this for the methodology for determining the ancestral hyplotype:
There is a wide variation when comparing two people. Close cousins can differ more than very distant cousins. However, once you have the ancestral haplotype, you can compare each to it and the matches will be tighter.