Cities are leading actions against climate change through global networks. More than 360 global cities announced during the 2015 Paris Climate Conference that the collective impact of their commitments will deliver over half of the world's urban greenhouse gas emissions reductions by 2020. Previous studies on multi-city carbon footprint networks using sub-national, multi-region input-output (MRIO) modelling have identified additional opportunities for addressing the negative impacts of climate change through joint actions between cities within a country. However, similar links between city carbon footprints have not yet been studied across countries. In this study we focus on inter-city and inter-country carbon flows between two trading partners in a first attempt to address this gap. We construct a multi-scale, global MRIO model to describe a transnational city carbon footprint network among five Chinese megacities and the five largest Australian capital cities. First, we quantify city carbon footprints by sectors and regions. Based on the carbon map concept we show how local emissions reductions influence other regions' carbon footprints. We then present a city emissions 'outsourcing hierarchy' based on the balance of emissions embodied in intercity and international trade. The differences between cities and their position in the hierarchy emphasize the need for a bespoke treatment of their responsibilities towards climate change mitigation. Finally, we evaluate and discuss the potentially significant benefits of harmonising and aligning China's carbon trading schemes with Australia's cap and trade policy.