The effects of carbon dioxide in the atmosphere can be reduced by closing anthropogenic cycles, and the methanation of carbon dioxide with hydrogen provides a promising option. Nevertheless, the reaction mechanism of this system is under discussion. The proposal of new pathways and the discussion of their feasibility can be structured with the application of P-graphs, to perform a combinatorially complete search of pathways in the first step of a kinetic study. By imposing constraints, the searching algorithm allows to compose feasible pathways. These constraints include mass balances and the existence of known intermediates. The search domain to find feasible pathways in the methanation of carbon dioxide can be reduced with the use of reaction blocks. No feasible pathways are lost in this process. The set of possible mechanisms have been reduced from 31 billion to 71 possible pathways, presented as an option to explain the reaction mechanism in this system.