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.

$\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$ Nov 24, 2016 at 7:42

1 Answer 1

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.

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

Your Answer

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

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