I am EXTREMELY confused on where to start with this problem. We recently just started learning about graph theory and I don't know where to begin.

Prove that in a connected graph G with $p$ vertices, $q$ edges, and at least one cycle, $q \ge p$

How do I begin with this question? Any help would be greatly appreciated. Thank you so much.

  • 4
    $\begingroup$ I suggest familiarising yourself with the graph theory definitions (there are several equivalent characterisations) of "tree", and in particular convincing yourself that they really "work in both directions". The claim in your question will then seem much clearer :) $\endgroup$ – j_random_hacker Nov 24 '16 at 7:42

Graph has a cycle on $k$ vertices implies that those vertices are connected with $k$ edges. Also, the graph is connected so $p-k$ vertices which left should be connected to the cycle, that means extra $p-k$ edges (distinct end points). Totally the graph has more($\geq$) than $p$ edges.

  • $\begingroup$ Correct if you change "more than $p$" to "at least $p$". $\endgroup$ – j_random_hacker Nov 24 '16 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.