Here is another idea which may get $k$ down to around $(b\log b)/m$. Start by picking $k = \lceil b/m \rceil$ and create a graphical fragment using $k$ columns. Hook up as many of these as you can to reduce the maximal number of unconnected edges at any vertex. Now double the fragment and hook up remaining edges between fragments. Iterate the doubling process until done. This may end up terminating quickly. Gerhard "Leaves The Analysis To You" Paseman, 2015.10.30.

Another obvious observation is that $km \gt b$. This really hinges on the maximal degree. It may be worth expressing $k$ as a function of $b/m$. Gerhard "Happy All Hallows Eve Eve" Paseman, 2015.10.30

Uh, if $q=1$, the group is no longer infinitely generated. I think the condition $1 \lt q \lt p$ shows where the interesting part is. I do like that your answer does cover the case $q=1$. Gerhard "For My Idea Of Interesting" Paseman, 2015.10.30

Is $X$ the set of degree values? If so, and if $b$ is the largest value of $X$, then in general $k \leq b$ (need $b+1$ when $M$ is a singleton). Gerhard "Will Add More With Confirmation" Paseman, 2015.10.30

I did, and it got reverted to Jamseon Thanks for the catch. Gerhard "Still Have Seoul Inside Me" Paseman, 2015.10.23

To my surprise, Jameson actually starts the notes using complex conjugate pairs. You might enjoy following the development for the first few pages. Gerhard "Maybe Complex Can Be Simpler" Paseman, 2015.10.21

I think students should note the following: I had some of the clues posted above before seeing Jameson's writeup, especially about using inversion and noting the improvement using prime powers. I didn't have 1.19, but might have developed it. The moral is to believe in the clues: I am surprised I got that close to a solution from just quick observations. Gerhard "Off To Observe Some More" Paseman, 2015.10.21

OK. If you change your mind, let me know by email. I will reference this MathOverflow answer in a write-up, and am willing to include real-life names (and some real beverages) to you and fedja as desired. Gerhard "Prefers An East Bay Visit" Paseman, 2015.10.20