Suppose a graph $G$ is connected with $n$ vertices and $e$ edges. If $n geq 3$ and $G$ has exactly one cycle,...












-1












$begingroup$


Suppose a graph $G$ is connected with $n$ vertices and $e$ edges. If $n ge 3$ and $G$ has exactly one cycle, prove that $e = n$.










share|cite|improve this question











$endgroup$












  • $begingroup$
    You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance.
    $endgroup$
    – Shaun
    Dec 8 '18 at 12:43
















-1












$begingroup$


Suppose a graph $G$ is connected with $n$ vertices and $e$ edges. If $n ge 3$ and $G$ has exactly one cycle, prove that $e = n$.










share|cite|improve this question











$endgroup$












  • $begingroup$
    You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance.
    $endgroup$
    – Shaun
    Dec 8 '18 at 12:43














-1












-1








-1





$begingroup$


Suppose a graph $G$ is connected with $n$ vertices and $e$ edges. If $n ge 3$ and $G$ has exactly one cycle, prove that $e = n$.










share|cite|improve this question











$endgroup$




Suppose a graph $G$ is connected with $n$ vertices and $e$ edges. If $n ge 3$ and $G$ has exactly one cycle, prove that $e = n$.







graph-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 8 '18 at 12:51









amWhy

1




1










asked Dec 8 '18 at 12:31









Siddiqa AlhaykiSiddiqa Alhayki

72




72












  • $begingroup$
    You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance.
    $endgroup$
    – Shaun
    Dec 8 '18 at 12:43


















  • $begingroup$
    You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance.
    $endgroup$
    – Shaun
    Dec 8 '18 at 12:43
















$begingroup$
You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance.
$endgroup$
– Shaun
Dec 8 '18 at 12:43




$begingroup$
You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance.
$endgroup$
– Shaun
Dec 8 '18 at 12:43










2 Answers
2






active

oldest

votes


















2












$begingroup$

Let $C$ be the only cycle in $G$. Consider any two adjacent vertices $u$ & $v$ that belong to $C$. Even if I remove the edge between $u$ & $v$, $G$ will remain connected. Let $G'$ be the new graph after removing the edge $uv$. $G'$ is connected, and has no cycle (bcoz we removed the $uv$ edge), hence $G'$ is a tree. $G'$ has $n-1$ edges $implies$ $G$ has $n$ edges.






share|cite|improve this answer









$endgroup$





















    0












    $begingroup$

    Consider the spanning tree of the graph $G$, The number of edges in the spanning tree is $n-1$. As $G$ has only one cycle, we can add only one more edge to the spanning tree to get the cycle(as any edges added to the spanning tree create a cycle), so $G$ has $n$ edges.






    share|cite|improve this answer









    $endgroup$













      Your Answer





      StackExchange.ifUsing("editor", function () {
      return StackExchange.using("mathjaxEditing", function () {
      StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
      StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
      });
      });
      }, "mathjax-editing");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "69"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      autoActivateHeartbeat: false,
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      noCode: true, onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031053%2fsuppose-a-graph-g-is-connected-with-n-vertices-and-e-edges-if-n-geq-3%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      2












      $begingroup$

      Let $C$ be the only cycle in $G$. Consider any two adjacent vertices $u$ & $v$ that belong to $C$. Even if I remove the edge between $u$ & $v$, $G$ will remain connected. Let $G'$ be the new graph after removing the edge $uv$. $G'$ is connected, and has no cycle (bcoz we removed the $uv$ edge), hence $G'$ is a tree. $G'$ has $n-1$ edges $implies$ $G$ has $n$ edges.






      share|cite|improve this answer









      $endgroup$


















        2












        $begingroup$

        Let $C$ be the only cycle in $G$. Consider any two adjacent vertices $u$ & $v$ that belong to $C$. Even if I remove the edge between $u$ & $v$, $G$ will remain connected. Let $G'$ be the new graph after removing the edge $uv$. $G'$ is connected, and has no cycle (bcoz we removed the $uv$ edge), hence $G'$ is a tree. $G'$ has $n-1$ edges $implies$ $G$ has $n$ edges.






        share|cite|improve this answer









        $endgroup$
















          2












          2








          2





          $begingroup$

          Let $C$ be the only cycle in $G$. Consider any two adjacent vertices $u$ & $v$ that belong to $C$. Even if I remove the edge between $u$ & $v$, $G$ will remain connected. Let $G'$ be the new graph after removing the edge $uv$. $G'$ is connected, and has no cycle (bcoz we removed the $uv$ edge), hence $G'$ is a tree. $G'$ has $n-1$ edges $implies$ $G$ has $n$ edges.






          share|cite|improve this answer









          $endgroup$



          Let $C$ be the only cycle in $G$. Consider any two adjacent vertices $u$ & $v$ that belong to $C$. Even if I remove the edge between $u$ & $v$, $G$ will remain connected. Let $G'$ be the new graph after removing the edge $uv$. $G'$ is connected, and has no cycle (bcoz we removed the $uv$ edge), hence $G'$ is a tree. $G'$ has $n-1$ edges $implies$ $G$ has $n$ edges.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Dec 8 '18 at 12:47









          Ankit KumarAnkit Kumar

          1,367219




          1,367219























              0












              $begingroup$

              Consider the spanning tree of the graph $G$, The number of edges in the spanning tree is $n-1$. As $G$ has only one cycle, we can add only one more edge to the spanning tree to get the cycle(as any edges added to the spanning tree create a cycle), so $G$ has $n$ edges.






              share|cite|improve this answer









              $endgroup$


















                0












                $begingroup$

                Consider the spanning tree of the graph $G$, The number of edges in the spanning tree is $n-1$. As $G$ has only one cycle, we can add only one more edge to the spanning tree to get the cycle(as any edges added to the spanning tree create a cycle), so $G$ has $n$ edges.






                share|cite|improve this answer









                $endgroup$
















                  0












                  0








                  0





                  $begingroup$

                  Consider the spanning tree of the graph $G$, The number of edges in the spanning tree is $n-1$. As $G$ has only one cycle, we can add only one more edge to the spanning tree to get the cycle(as any edges added to the spanning tree create a cycle), so $G$ has $n$ edges.






                  share|cite|improve this answer









                  $endgroup$



                  Consider the spanning tree of the graph $G$, The number of edges in the spanning tree is $n-1$. As $G$ has only one cycle, we can add only one more edge to the spanning tree to get the cycle(as any edges added to the spanning tree create a cycle), so $G$ has $n$ edges.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Dec 8 '18 at 19:39









                  nafhgoodnafhgood

                  1,801422




                  1,801422






























                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Mathematics Stack Exchange!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      Use MathJax to format equations. MathJax reference.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3031053%2fsuppose-a-graph-g-is-connected-with-n-vertices-and-e-edges-if-n-geq-3%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      Popular posts from this blog

                      Berounka

                      Sphinx de Gizeh

                      Different font size/position of beamer's navigation symbols template's content depending on regular/plain...