Much effort has been spent to investigate catalytic generation of hydrogen from methanol partial oxidation (MPO) in light of its practical and theoretical importance. Nevertheless, relatively little has been done to gain in-depth understanding of the catalytic mechanisms or pathways of MPO. The exploration of pathways of any catalytic reaction can be greatly facilitated by exhaustively generating at the outset stoichiometrically feasible and independent catalytic mechanisms or pathways (IPi's) from a set of plausible elementary reactions by means of our graph-theoretic method based on P-graphs (process graphs). The method is implemented by resorting to the combinatorial algorithms derived from the two sets of rigorously stated axioms on the basis of the mass-conservation law and stoichiometric principle. In the current work, a set of 13 plausible elementary reactions has been proposed for MPO from which six IPi's have been generated in less than 1 s with a PC (Pentium 4, CPU 3.06 GHz, and 1 GB RAM). Subsequently, the rate equations of these six IPi's have been derived according to the Langmuir-Hinshelwood-Hougen-Watson (LHHW) formalism. The kinetic constants of the resultant rate equations have been estimated through nonlinear regression of the equations with experimental data. In light of the least-square criterion, IP2 and IP6 are deemed potentially dominant pathways.