1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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, 2016 at 7:42

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Correct if you change "more than $p$" to "at least $p$". $\endgroup$
    – j_random_hacker
    Nov 24, 2016 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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