How to prove that at least two vertices have the same degree in any graph?












5












$begingroup$


I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?






combinatorics discrete-mathematics graph-theory







share|cite|improve this question











$endgroup$












  • $begingroup$
    Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
    $endgroup$
    – Shaun
    9 hours ago






  • 1




    $begingroup$
    Symmetric, simple graphs?
    $endgroup$
    – Mindlack
    9 hours ago






  • 2




    $begingroup$
    Possible duplicate of "In a party people shake hands with one another"
    $endgroup$
    – JMoravitz
    8 hours ago










  • $begingroup$
    Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
    $endgroup$
    – Acccumulation
    4 hours ago


















5












$begingroup$


I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?






combinatorics discrete-mathematics graph-theory







share|cite|improve this question











$endgroup$












  • $begingroup$
    Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
    $endgroup$
    – Shaun
    9 hours ago






  • 1




    $begingroup$
    Symmetric, simple graphs?
    $endgroup$
    – Mindlack
    9 hours ago






  • 2




    $begingroup$
    Possible duplicate of "In a party people shake hands with one another"
    $endgroup$
    – JMoravitz
    8 hours ago










  • $begingroup$
    Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
    $endgroup$
    – Acccumulation
    4 hours ago
















5












5








5


1



$begingroup$


I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?






combinatorics discrete-mathematics graph-theory







share|cite|improve this question











$endgroup$




I want to prove that at least two vertices have the same degree in any graph (with 2 or more vertices). I do have a few graphs in mind that prove this statement correct, but how would I go about proving it (or disproving it) for ALL graphs?






combinatorics discrete-mathematics graph-theory




combinatorics discrete-mathematics graph-theory






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 2 hours ago









James Rettie

31




31










asked 9 hours ago









desiignerdesiigner

575




575












  • $begingroup$
    Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
    $endgroup$
    – Shaun
    9 hours ago






  • 1




    $begingroup$
    Symmetric, simple graphs?
    $endgroup$
    – Mindlack
    9 hours ago






  • 2




    $begingroup$
    Possible duplicate of "In a party people shake hands with one another"
    $endgroup$
    – JMoravitz
    8 hours ago










  • $begingroup$
    Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
    $endgroup$
    – Acccumulation
    4 hours ago




















  • $begingroup$
    Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
    $endgroup$
    – Shaun
    9 hours ago






  • 1




    $begingroup$
    Symmetric, simple graphs?
    $endgroup$
    – Mindlack
    9 hours ago






  • 2




    $begingroup$
    Possible duplicate of "In a party people shake hands with one another"
    $endgroup$
    – JMoravitz
    8 hours ago










  • $begingroup$
    Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
    $endgroup$
    – Acccumulation
    4 hours ago


















$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
9 hours ago




$begingroup$
Please try to make the titles of your questions more informative. For example, Why does $a<b$ imply $a+c<b+c$? is much more useful for other users than A question about inequality. From How can I ask a good question?: Make your title as descriptive as possible. In many cases one can actually phrase the title as the question, at least in such a way so as to be comprehensible to an expert reader. You can find more tips for choosing a good title here.
$endgroup$
– Shaun
9 hours ago




1




1




$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
9 hours ago




$begingroup$
Symmetric, simple graphs?
$endgroup$
– Mindlack
9 hours ago




2




2




$begingroup$
Possible duplicate of "In a party people shake hands with one another"
$endgroup$
– JMoravitz
8 hours ago




$begingroup$
Possible duplicate of "In a party people shake hands with one another"
$endgroup$
– JMoravitz
8 hours ago












$begingroup$
Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
$endgroup$
– Acccumulation
4 hours ago






$begingroup$
Possible duplicate of If n is a natural number ≥2 how do I prove that any graph with n vertices has at least two vertices of the same degree?
$endgroup$
– Acccumulation
4 hours ago












3 Answers
3






active

oldest

votes


















10












$begingroup$

Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$



So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Perhaps it would be better to include that the graph is simple?
    $endgroup$
    – Shubham Johri
    8 hours ago










  • $begingroup$
    Is it necessary to specify "no loops"?
    $endgroup$
    – Shufflepants
    4 hours ago










  • $begingroup$
    Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
    $endgroup$
    – greedoid
    4 hours ago








  • 1




    $begingroup$
    @greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
    $endgroup$
    – Shufflepants
    4 hours ago










  • $begingroup$
    Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
    $endgroup$
    – immibis
    2 hours ago





















8












$begingroup$

I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.



Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.






share|cite|improve this answer








New contributor




Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






$endgroup$













  • $begingroup$
    You are assuming the graph is simple?
    $endgroup$
    – Servaes
    4 hours ago










  • $begingroup$
    Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
    $endgroup$
    – Robert Shore
    3 hours ago



















0












$begingroup$

Here is a counterexample.



Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.



Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that



$$j < k$$
$$lfloor j/2 rfloor le lfloor k/2 rfloor$$
$$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
$$deg(j) < deg(k)$$
$$deg(j) neq deg(k)$$



Therefore, no two different vertices will have the same degree. $square$






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%2f3100174%2fhow-to-prove-that-at-least-two-vertices-have-the-same-degree-in-any-graph%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    10












    $begingroup$

    Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$



    So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Perhaps it would be better to include that the graph is simple?
      $endgroup$
      – Shubham Johri
      8 hours ago










    • $begingroup$
      Is it necessary to specify "no loops"?
      $endgroup$
      – Shufflepants
      4 hours ago










    • $begingroup$
      Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
      $endgroup$
      – greedoid
      4 hours ago








    • 1




      $begingroup$
      @greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
      $endgroup$
      – Shufflepants
      4 hours ago










    • $begingroup$
      Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
      $endgroup$
      – immibis
      2 hours ago


















    10












    $begingroup$

    Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$



    So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.






    share|cite|improve this answer











    $endgroup$













    • $begingroup$
      Perhaps it would be better to include that the graph is simple?
      $endgroup$
      – Shubham Johri
      8 hours ago










    • $begingroup$
      Is it necessary to specify "no loops"?
      $endgroup$
      – Shufflepants
      4 hours ago










    • $begingroup$
      Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
      $endgroup$
      – greedoid
      4 hours ago








    • 1




      $begingroup$
      @greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
      $endgroup$
      – Shufflepants
      4 hours ago










    • $begingroup$
      Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
      $endgroup$
      – immibis
      2 hours ago
















    10












    10








    10





    $begingroup$

    Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$



    So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.






    share|cite|improve this answer











    $endgroup$



    Say graph is simple with no loops and that all vertices have different degree $d_1,d_2,...d_n$, then $${d_1,d_2,...d_n} = {0,1,2...,n-1}$$



    So there is a vertex with degree $n-1$ and a vertex with degree $0$. A contradiction.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited 8 hours ago

























    answered 9 hours ago









    greedoidgreedoid

    41k1149101




    41k1149101












    • $begingroup$
      Perhaps it would be better to include that the graph is simple?
      $endgroup$
      – Shubham Johri
      8 hours ago










    • $begingroup$
      Is it necessary to specify "no loops"?
      $endgroup$
      – Shufflepants
      4 hours ago










    • $begingroup$
      Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
      $endgroup$
      – greedoid
      4 hours ago








    • 1




      $begingroup$
      @greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
      $endgroup$
      – Shufflepants
      4 hours ago










    • $begingroup$
      Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
      $endgroup$
      – immibis
      2 hours ago




















    • $begingroup$
      Perhaps it would be better to include that the graph is simple?
      $endgroup$
      – Shubham Johri
      8 hours ago










    • $begingroup$
      Is it necessary to specify "no loops"?
      $endgroup$
      – Shufflepants
      4 hours ago










    • $begingroup$
      Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
      $endgroup$
      – greedoid
      4 hours ago








    • 1




      $begingroup$
      @greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
      $endgroup$
      – Shufflepants
      4 hours ago










    • $begingroup$
      Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
      $endgroup$
      – immibis
      2 hours ago


















    $begingroup$
    Perhaps it would be better to include that the graph is simple?
    $endgroup$
    – Shubham Johri
    8 hours ago




    $begingroup$
    Perhaps it would be better to include that the graph is simple?
    $endgroup$
    – Shubham Johri
    8 hours ago












    $begingroup$
    Is it necessary to specify "no loops"?
    $endgroup$
    – Shufflepants
    4 hours ago




    $begingroup$
    Is it necessary to specify "no loops"?
    $endgroup$
    – Shufflepants
    4 hours ago












    $begingroup$
    Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
    $endgroup$
    – greedoid
    4 hours ago






    $begingroup$
    Of course. Take a graph with two vertices and one connected to it self. @Shufflepants
    $endgroup$
    – greedoid
    4 hours ago






    1




    1




    $begingroup$
    @greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
    $endgroup$
    – Shufflepants
    4 hours ago




    $begingroup$
    @greedoid Then by "no loops" did you mean "no self connection"? Otherwise I'd interpret "simple with no loops" as being equivalent to a tree. But in any case, the OP didn't specify "simple" or "no loops". So, it would seem the answer to the question is: it's not provable because it's not true.
    $endgroup$
    – Shufflepants
    4 hours ago












    $begingroup$
    Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
    $endgroup$
    – immibis
    2 hours ago






    $begingroup$
    Because I didn't see it at first: This follows because in a simple graph the degree of any vertex must be less than the number of vertices. Thus if the vertex degrees are all different and less than $n$ they must be ${0, 1, 2..., n-1}$.
    $endgroup$
    – immibis
    2 hours ago













    8












    $begingroup$

    I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.



    Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.






    share|cite|improve this answer








    New contributor




    Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    $endgroup$













    • $begingroup$
      You are assuming the graph is simple?
      $endgroup$
      – Servaes
      4 hours ago










    • $begingroup$
      Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
      $endgroup$
      – Robert Shore
      3 hours ago
















    8












    $begingroup$

    I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.



    Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.






    share|cite|improve this answer








    New contributor




    Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    $endgroup$













    • $begingroup$
      You are assuming the graph is simple?
      $endgroup$
      – Servaes
      4 hours ago










    • $begingroup$
      Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
      $endgroup$
      – Robert Shore
      3 hours ago














    8












    8








    8





    $begingroup$

    I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.



    Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.






    share|cite|improve this answer








    New contributor




    Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    $endgroup$



    I assume we're talking about finite graphs. I'm pretty sure your statement is false for infinite graphs.



    Assume that a finite graph $G$ has $n$ vertices. Then each vertex has a degree between $n-1$ and $0$. But if any vertex has degree $0$, then no vertex can have degree $n-1$, so it's not possible for the degrees of the graph's vertices to include both $0$ and $n-1$. Thus, the $n$ vertices of the graph can only have $n-1$ different degrees, so by the pigeonhole principle at least two vertices must have the same degree.







    share|cite|improve this answer








    New contributor




    Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    share|cite|improve this answer



    share|cite|improve this answer






    New contributor




    Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    answered 8 hours ago









    Robert ShoreRobert Shore

    1915




    1915




    New contributor




    Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.





    New contributor





    Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    Robert Shore is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.












    • $begingroup$
      You are assuming the graph is simple?
      $endgroup$
      – Servaes
      4 hours ago










    • $begingroup$
      Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
      $endgroup$
      – Robert Shore
      3 hours ago


















    • $begingroup$
      You are assuming the graph is simple?
      $endgroup$
      – Servaes
      4 hours ago










    • $begingroup$
      Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
      $endgroup$
      – Robert Shore
      3 hours ago
















    $begingroup$
    You are assuming the graph is simple?
    $endgroup$
    – Servaes
    4 hours ago




    $begingroup$
    You are assuming the graph is simple?
    $endgroup$
    – Servaes
    4 hours ago












    $begingroup$
    Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
    $endgroup$
    – Robert Shore
    3 hours ago




    $begingroup$
    Yes. That is assumed in the definition of graph that I learned. I learned to call a graph with loops or multiple edges between vertices a "multigraph."
    $endgroup$
    – Robert Shore
    3 hours ago











    0












    $begingroup$

    Here is a counterexample.



    Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.



    Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that



    $$j < k$$
    $$lfloor j/2 rfloor le lfloor k/2 rfloor$$
    $$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
    $$deg(j) < deg(k)$$
    $$deg(j) neq deg(k)$$



    Therefore, no two different vertices will have the same degree. $square$






    share|cite|improve this answer









    $endgroup$


















      0












      $begingroup$

      Here is a counterexample.



      Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.



      Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that



      $$j < k$$
      $$lfloor j/2 rfloor le lfloor k/2 rfloor$$
      $$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
      $$deg(j) < deg(k)$$
      $$deg(j) neq deg(k)$$



      Therefore, no two different vertices will have the same degree. $square$






      share|cite|improve this answer









      $endgroup$
















        0












        0








        0





        $begingroup$

        Here is a counterexample.



        Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.



        Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that



        $$j < k$$
        $$lfloor j/2 rfloor le lfloor k/2 rfloor$$
        $$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
        $$deg(j) < deg(k)$$
        $$deg(j) neq deg(k)$$



        Therefore, no two different vertices will have the same degree. $square$






        share|cite|improve this answer









        $endgroup$



        Here is a counterexample.



        Let $G$ be a graph on the positive integers where there is an edge from $x$ to $y$ if $x < y le 2x$. Note that we will ignore the direction of the edges. So $2$, for example, is neighbored by $1$, $3$, and $4$.



        Let $j$ and $k$ be distinct positive integers. Without loss of generality assume that $j < k$. Note that $deg(j) = j + lfloor j/2 rfloor$ and $deg(k) = k + lfloor k/2 rfloor$. We have that



        $$j < k$$
        $$lfloor j/2 rfloor le lfloor k/2 rfloor$$
        $$j + lfloor j/2 rfloor < k + lfloor k/2 rfloor$$
        $$deg(j) < deg(k)$$
        $$deg(j) neq deg(k)$$



        Therefore, no two different vertices will have the same degree. $square$







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 4 hours ago









        PyRulezPyRulez

        4,68622469




        4,68622469






























            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%2f3100174%2fhow-to-prove-that-at-least-two-vertices-have-the-same-degree-in-any-graph%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

            Contact image not getting when fetch all contact list from iPhone by CNContact

            Image
            up vote 0 down vote favorite I know this question already asked but not getting solution. From this code I will get all the information from the contact but image not found when open vcf files on mac os, also not getting when share this file. I use this stackoverflow link here but It's not help full. var contacts = [CNContact]() let keys = [CNContactVCardSerialization.descriptorForRequiredKeys() ] as [Any] let request = CNContactFetchRequest(keysToFetch: keys as! [CNKeyDescriptor]) do { try self.contactStore.enumerateContacts(with: request) { (contact, stop) in // Array containing all unified contacts from everywhere contacts.append(contact) } } catch { print("unable to fetch contacts") } do { let data = try
            Read more

            count number of partitions of a set with n elements into k subsets

            Image
            up vote 6 down vote favorite 1 This program is for count number of partitions of a set with n elements into k subsets I am confusing here return k*countP(n-1, k) + countP(n-1, k-1); can some one explain what is happening here? why we are multiplying with k? NOTE->I know this is not the best way to calculate number of partitions that would be DP // A C++ program to count number of partitions // of a set with n elements into k subsets #include<iostream> using namespace std; // Returns count of different partitions of n // elements in k subsets int countP(int n, int k) { // Base cases if (n == 0 || k == 0 || k > n) return 0; if (k == 1 || k == n) return 1; // S(n+1, k) = k*S(n, k) + S(n, k-1) return k*countP(n-1, k) + countP(n-1, k-1); } // Driver program int ma
            Read more

            A CLEAN and SIMPLE way to add appendices to Table of Contents and bookmarks

            Image
            0 I found a lot of questions abount appendices and ToC. Many users want appendices to be grouped in an Appendix part, however some problems arise with ToC, hyperref, PDF viewer bookmarks, and so on. There are different solutions which require extra packages, command patching and other extra code, however none of them satisfies me. I almost found an easy way to accomplish a good result, where appendices are added to bookmarks in the right way and hyperref links point to the right page. However, the number of the "Appendix" part page is wrong (it's the number of appendix A). Is there any EASY way to fix that? This is a MWE: documentclass{book} usepackage[nottoc,notlot,notlof]{tocbibind} usepackage{hyperref} begin{document} frontmatter tableofcontents mainmatter part{First} chapter{
            Read more