How do I check if a menu exists?

Assuming that you have custom Nav Menus implemented properly:

1. Registering nav menu Theme Locations:

   register_nav_menus( array(
       'parent_page' => "Parent Page",
       'page_a' => "Page A",
       'page_b' => "Page B", //etc
   ) );
   

2. Calling wp_nav_menu() correctly:

   wp_nav_menu( array(
       'theme_location' => 'page_a'
   );
   

…then you can use the has_nav_menu() conditional to determine if a Theme Location has a menu assigned to it:

if ( has_nav_menu( 'page_a' ) ) {
    // do something
}

In your specific case, you could do something like so:

if ( has_nav_menu( 'page_a' ) ) {
    wp_nav_menu( array( 'theme_location' => 'page_a' ) );
} else {
    wp_nav_menu( array( 'theme_location' => 'parent_page' ) );
}