Direct growth of graphene integrated into electronic devices is highly desirable but difficult due to the nominal ~1000 °C chemical vapor deposition (CVD) temperature, which can seriously deteriorate the substrates. Here we report a great reduction of graphene CVD temperature, down to 50 °C on sapphire and 100 °C on polycarbonate, by using dilute methane as the source and molten gallium (Ga) as catalysts. The very low temperature graphene synthesis is made possible by carbon attachment to the island edges of pre-existing graphene nuclei islands, and causes no damages to the substrates. A key benefit of using molten Ga catalyst is the enhanced methane absorption in Ga at lower temperatures; this leads to a surprisingly low apparent reaction barrier of ~0.16 eV below 300 °C. The faster growth kinetics due to a low reaction barrier and a demonstrated low-temperature graphene nuclei transfer protocol can facilitate practical direct graphene synthesis on many kinds of substrates down to 50-100 °C. Our results represent a significant progress in reducing graphene synthesis temperature and understanding its mechanism.