There are issues of identification of key nodes in cross-regional consumption of renewable energy, in rapid assessment of the maximum transmission quota, and in the collection and allocation of transmission costs. Thus this paper proposes a cross-regional transaction path Transmission Cost Allocation (TCA) strategy based on a graph-theory network-flow algorithm. First, this paper builds a simplified graph model of the UHV network from the perspective of pure topological structure, analyzes the network connectivity of the simplified graph, and obtains the identification of the key nodes in the system. Secondly, the source and sink nodes are set corresponding to the electricity sellers and buyers in the transaction path, and to increase the maximum feasible flow between the sources and sinks by the Edmond-Karp algorithm. The search for augmenting path realizes an effective and rapid estimation of the maximum delivery amount of the transaction path. Finally, a case study is carried out on the Qinghai-Hunan renewable-energy consumption transaction path through graph theory based TCA, and the results of the current transaction path are introduced to verify the effectiveness, rationality and feasibility of the algorithm. This work is supported by the Science and Technology Project of State Grid Corporation of China “Promote the Key Technologies Research and Application of Inter-Provincial Incremental Allocation of Spot Electricity Market for Renewable Energy Consumption” (No. SGJS0000DKJS1900147).