It is quite usual for part or all of the catering to be removed as the first resort if the aircraft is over maximum zero fuel weight or max takeoff weight. This is usually considered more desirable than off loading bags or passengers. So what they say is very feasible.