Accurate knowledge of natural gas network topology is critical for the proper operation of natural gas networks. Failures, physical attacks, and cyber attacks can cause the actual natural gas network topology to differ from what the operator believes to be present. Incorrect topology information misleads the operator to apply inappropriate control causing damage and lack of gas supply. Several methods for verifying the topology have been suggested in the literature for electrical power distribution networks, but we are not aware of any publications for natural gas networks. In this paper, we develop a useful topology verification algorithm for natural gas networks based on modifying a general known statistics-based approach to eliminate serious limitations for this application while maintaining good performance. We prove that the new algorithm is equivalent to the original statistics-based approach for a sufficiently large number of sensor observations. We provide new closed-form expressions for the asymptotic performance that are shown to be accurate for the typical number of sensor observations required to achieve reliable performance.