A network verification system verifies a network to which a relay apparatus relays a packet. A test management apparatus includes a condition acquiring unit to acquire verification conditions which contain an unused network address as a test target and a registering unit to register, in an address resolution table of the relay apparatus, an entry in which the unused network address contained in the acquired verification conditions is associated with a physical address of the testing apparatus. A testing apparatus includes a test packet transmitting unit to transmit, when instructed by the test management apparatus, the plurality of test packets to form a plurality of connections based on the verification conditions, a test packet receiving unit to receive the plurality of test packets and a measuring unit to measure communication qualities with respect to the respective connections of the plurality of test packets.