Minimum cardinal number of a set contains all the paths of a complete bi-partite graph












1












$begingroup$


What is the minimum cardinal number of a set contains all the paths of a complete bi-partite graph: K(7,10), where every edge of the graph must be in one (and only one) of these paths.
how can I construct this set and how can I prove that a smaller set doesn't exsist?



basically I not sure how to do It, but I thought about something hoping that someone could verify my progress:



I think that the minimum cardinal number of such set must be 5, because if the minimum cardinal number was at least 4, then I had at least 4 paths => I had at least 8 vertices which are the beginning or the end of some path, which means I had at least 17 - 8 = 9 vertices where the paths are "using" only an even number of edges passing through the vertices and that's a contradiction because I have 9 vertices with the above condition I can choose a vertex from the 10 vertices "side" and because each vertex in that side connects to 7 vertices which is an odd number, such set could not be.



(I Know it's not the most rigorous proof but that's why I'm asking for help)










share|cite|improve this question











$endgroup$

















    1












    $begingroup$


    What is the minimum cardinal number of a set contains all the paths of a complete bi-partite graph: K(7,10), where every edge of the graph must be in one (and only one) of these paths.
    how can I construct this set and how can I prove that a smaller set doesn't exsist?



    basically I not sure how to do It, but I thought about something hoping that someone could verify my progress:



    I think that the minimum cardinal number of such set must be 5, because if the minimum cardinal number was at least 4, then I had at least 4 paths => I had at least 8 vertices which are the beginning or the end of some path, which means I had at least 17 - 8 = 9 vertices where the paths are "using" only an even number of edges passing through the vertices and that's a contradiction because I have 9 vertices with the above condition I can choose a vertex from the 10 vertices "side" and because each vertex in that side connects to 7 vertices which is an odd number, such set could not be.



    (I Know it's not the most rigorous proof but that's why I'm asking for help)










    share|cite|improve this question











    $endgroup$















      1












      1








      1





      $begingroup$


      What is the minimum cardinal number of a set contains all the paths of a complete bi-partite graph: K(7,10), where every edge of the graph must be in one (and only one) of these paths.
      how can I construct this set and how can I prove that a smaller set doesn't exsist?



      basically I not sure how to do It, but I thought about something hoping that someone could verify my progress:



      I think that the minimum cardinal number of such set must be 5, because if the minimum cardinal number was at least 4, then I had at least 4 paths => I had at least 8 vertices which are the beginning or the end of some path, which means I had at least 17 - 8 = 9 vertices where the paths are "using" only an even number of edges passing through the vertices and that's a contradiction because I have 9 vertices with the above condition I can choose a vertex from the 10 vertices "side" and because each vertex in that side connects to 7 vertices which is an odd number, such set could not be.



      (I Know it's not the most rigorous proof but that's why I'm asking for help)










      share|cite|improve this question











      $endgroup$




      What is the minimum cardinal number of a set contains all the paths of a complete bi-partite graph: K(7,10), where every edge of the graph must be in one (and only one) of these paths.
      how can I construct this set and how can I prove that a smaller set doesn't exsist?



      basically I not sure how to do It, but I thought about something hoping that someone could verify my progress:



      I think that the minimum cardinal number of such set must be 5, because if the minimum cardinal number was at least 4, then I had at least 4 paths => I had at least 8 vertices which are the beginning or the end of some path, which means I had at least 17 - 8 = 9 vertices where the paths are "using" only an even number of edges passing through the vertices and that's a contradiction because I have 9 vertices with the above condition I can choose a vertex from the 10 vertices "side" and because each vertex in that side connects to 7 vertices which is an odd number, such set could not be.



      (I Know it's not the most rigorous proof but that's why I'm asking for help)







      combinatorics general-topology graph-theory bipartite-graph






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Jan 12 at 0:22







      MercyDude

















      asked Jan 11 at 22:49









      MercyDudeMercyDude

      1484




      1484






















          2 Answers
          2






          active

          oldest

          votes


















          2












          $begingroup$

          Let's start by clarifying the problem statement.



          In the title, and again in the first line of the question, you say you want a set that "contains all the paths" but it's clear that you don't mean that; what you want is a set of paths containing all the edges.



          In a comment you say the paths don't have to be "simple paths". In most (not all) books on graph theory, "path" means "simple path"; a path may not repeat edges or vertices. If you are going to use some unusual terminology, you need to tell us about it, so we will know what you're talking about. So your "paths" do not have to be simple. However, if you allowed vertices and edges to be repeated, then one long "path" would do the job. So I guess your "path" is allowed to repeat vertices but not edges. In graph theory, a walk which may repeat vertices but may not repeat edges is usually called a trail. Let me restate your question:




          What is the minimum number of edge-disjoint trails covering all the edges of the complete bipartite graph $K_{7,10}$?




          The answer (five) follows from a well known extension of the characterization of Eulerian graphs:



          Theorem. Let $k$ be a positive integer. Suppose a (finite) connected graph $G$ has exactly $2k$ vertices of odd degree. Then the edges of $G$ can be covered by $k$ (and no fewer) edge-disjoint trails.



          Proof. You can't do with fewer than $k$ trails, since each of the $2k$ odd degree vertices must be an endpoint of a trail. (You gave this argument in your question.) to see that $k$ trails suffice, add $k$ new edges to the graph, joining the odd-degree vertices in pairs. The resulting graph (which may have multiple edges, but that's O.K.) is connected, and has no vertices of odd degree. Therefore the new graph is Eulerian, meaning that it contains a circuit (i.e. a closed trail) which traverses each edge exactly once. When we remove the $k$ extra edges (to get back to the original graph), the circuit break up into $k$ trails, each of which connects a pair of odd-degree vertices.



          Your graph $K_{7,10}$ is connected and has $10$ vertices of odd degree, so it can be covered by $5$ edge-disjoint trails. If you want to construct a set of $5$ trails that works, I recommend using Hierholzer's algorithm to find an Euler circuit in the enlarged graph.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            That's awsome! Sorry for the bad terminology I don't study in English, you got that right.
            $endgroup$
            – MercyDude
            Jan 12 at 8:49










          • $begingroup$
            Btw, why adding only one extra vertex won't suffice ? adding one vertex and connecting it to each of the 10 vertices will upgrade their degree to an even one and therefore I can construct an Euler circuit, though I'm not sure how exactly.
            $endgroup$
            – MercyDude
            Jan 12 at 15:34










          • $begingroup$
            @MercyDude That will work too. Not sure why adding one vertex and $10$ edges is better than adding no vertex and $5$ edges. Did you read the Wikipedia page about constructing a circuit? The point is, if you've got a circuit that doesn't use all the edges, you can enlarge it by patching in another circuit. "Rinse and repeat."
            $endgroup$
            – bof
            Jan 12 at 15:47



















          0












          $begingroup$

          Every path in $K_{7,10}$ goes through at most $15$ points, since at least half of the vertices rounded down are in the part of size $7$. This means each path covers at most $14$ edges. Since $K_{7,10}$ has $70$ edges, it will take at least $70/14=5$ paths to include every edge of $K_{7,10}$.



          To show that $5$ is optimal, it suffices to list out $5$ paths which include each edge of $K_{7,10}$ exactly once. Here they are; one part is labeled with the digits $0$ to $9$, the other with letters $A$ to $G$.



          0 1 2 3 4 5 6 7
          |/|/|/|/|/|/|/
          A B C D E F G

          2 3 4 5 6 7 8 9
          |/|/|/|/|/|/|/
          A B C D E F G

          4 5 6 7 8 9 0 1
          |/|/|/|/|/|/|/
          A B C D E F G

          6 7 8 9 0 1 2 3
          |/|/|/|/|/|/|/
          A B C D E F G

          8 9 0 1 2 3 4 5
          |/|/|/|/|/|/|/
          A B C D E F G





          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Thanks, but why "Every path in K7,10 goes through at most 15 points" For example in your first path I can connect 7 to A (It doesn't have to be a simple path...)
            $endgroup$
            – MercyDude
            Jan 12 at 0:30






          • 2




            $begingroup$
            Gotcha, then my proof does not work. The proof in your post about the vertices in the 10 part having odd degree is correct, and proves the minimum possible cardinality is at least 5. The construction in my post proves the minimum is at most 5, so together you know the answer is 5.
            $endgroup$
            – Mike Earnest
            Jan 12 at 1:09











          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%2f3070412%2fminimum-cardinal-number-of-a-set-contains-all-the-paths-of-a-complete-bi-partite%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's start by clarifying the problem statement.



          In the title, and again in the first line of the question, you say you want a set that "contains all the paths" but it's clear that you don't mean that; what you want is a set of paths containing all the edges.



          In a comment you say the paths don't have to be "simple paths". In most (not all) books on graph theory, "path" means "simple path"; a path may not repeat edges or vertices. If you are going to use some unusual terminology, you need to tell us about it, so we will know what you're talking about. So your "paths" do not have to be simple. However, if you allowed vertices and edges to be repeated, then one long "path" would do the job. So I guess your "path" is allowed to repeat vertices but not edges. In graph theory, a walk which may repeat vertices but may not repeat edges is usually called a trail. Let me restate your question:




          What is the minimum number of edge-disjoint trails covering all the edges of the complete bipartite graph $K_{7,10}$?




          The answer (five) follows from a well known extension of the characterization of Eulerian graphs:



          Theorem. Let $k$ be a positive integer. Suppose a (finite) connected graph $G$ has exactly $2k$ vertices of odd degree. Then the edges of $G$ can be covered by $k$ (and no fewer) edge-disjoint trails.



          Proof. You can't do with fewer than $k$ trails, since each of the $2k$ odd degree vertices must be an endpoint of a trail. (You gave this argument in your question.) to see that $k$ trails suffice, add $k$ new edges to the graph, joining the odd-degree vertices in pairs. The resulting graph (which may have multiple edges, but that's O.K.) is connected, and has no vertices of odd degree. Therefore the new graph is Eulerian, meaning that it contains a circuit (i.e. a closed trail) which traverses each edge exactly once. When we remove the $k$ extra edges (to get back to the original graph), the circuit break up into $k$ trails, each of which connects a pair of odd-degree vertices.



          Your graph $K_{7,10}$ is connected and has $10$ vertices of odd degree, so it can be covered by $5$ edge-disjoint trails. If you want to construct a set of $5$ trails that works, I recommend using Hierholzer's algorithm to find an Euler circuit in the enlarged graph.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            That's awsome! Sorry for the bad terminology I don't study in English, you got that right.
            $endgroup$
            – MercyDude
            Jan 12 at 8:49










          • $begingroup$
            Btw, why adding only one extra vertex won't suffice ? adding one vertex and connecting it to each of the 10 vertices will upgrade their degree to an even one and therefore I can construct an Euler circuit, though I'm not sure how exactly.
            $endgroup$
            – MercyDude
            Jan 12 at 15:34










          • $begingroup$
            @MercyDude That will work too. Not sure why adding one vertex and $10$ edges is better than adding no vertex and $5$ edges. Did you read the Wikipedia page about constructing a circuit? The point is, if you've got a circuit that doesn't use all the edges, you can enlarge it by patching in another circuit. "Rinse and repeat."
            $endgroup$
            – bof
            Jan 12 at 15:47
















          2












          $begingroup$

          Let's start by clarifying the problem statement.



          In the title, and again in the first line of the question, you say you want a set that "contains all the paths" but it's clear that you don't mean that; what you want is a set of paths containing all the edges.



          In a comment you say the paths don't have to be "simple paths". In most (not all) books on graph theory, "path" means "simple path"; a path may not repeat edges or vertices. If you are going to use some unusual terminology, you need to tell us about it, so we will know what you're talking about. So your "paths" do not have to be simple. However, if you allowed vertices and edges to be repeated, then one long "path" would do the job. So I guess your "path" is allowed to repeat vertices but not edges. In graph theory, a walk which may repeat vertices but may not repeat edges is usually called a trail. Let me restate your question:




          What is the minimum number of edge-disjoint trails covering all the edges of the complete bipartite graph $K_{7,10}$?




          The answer (five) follows from a well known extension of the characterization of Eulerian graphs:



          Theorem. Let $k$ be a positive integer. Suppose a (finite) connected graph $G$ has exactly $2k$ vertices of odd degree. Then the edges of $G$ can be covered by $k$ (and no fewer) edge-disjoint trails.



          Proof. You can't do with fewer than $k$ trails, since each of the $2k$ odd degree vertices must be an endpoint of a trail. (You gave this argument in your question.) to see that $k$ trails suffice, add $k$ new edges to the graph, joining the odd-degree vertices in pairs. The resulting graph (which may have multiple edges, but that's O.K.) is connected, and has no vertices of odd degree. Therefore the new graph is Eulerian, meaning that it contains a circuit (i.e. a closed trail) which traverses each edge exactly once. When we remove the $k$ extra edges (to get back to the original graph), the circuit break up into $k$ trails, each of which connects a pair of odd-degree vertices.



          Your graph $K_{7,10}$ is connected and has $10$ vertices of odd degree, so it can be covered by $5$ edge-disjoint trails. If you want to construct a set of $5$ trails that works, I recommend using Hierholzer's algorithm to find an Euler circuit in the enlarged graph.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            That's awsome! Sorry for the bad terminology I don't study in English, you got that right.
            $endgroup$
            – MercyDude
            Jan 12 at 8:49










          • $begingroup$
            Btw, why adding only one extra vertex won't suffice ? adding one vertex and connecting it to each of the 10 vertices will upgrade their degree to an even one and therefore I can construct an Euler circuit, though I'm not sure how exactly.
            $endgroup$
            – MercyDude
            Jan 12 at 15:34










          • $begingroup$
            @MercyDude That will work too. Not sure why adding one vertex and $10$ edges is better than adding no vertex and $5$ edges. Did you read the Wikipedia page about constructing a circuit? The point is, if you've got a circuit that doesn't use all the edges, you can enlarge it by patching in another circuit. "Rinse and repeat."
            $endgroup$
            – bof
            Jan 12 at 15:47














          2












          2








          2





          $begingroup$

          Let's start by clarifying the problem statement.



          In the title, and again in the first line of the question, you say you want a set that "contains all the paths" but it's clear that you don't mean that; what you want is a set of paths containing all the edges.



          In a comment you say the paths don't have to be "simple paths". In most (not all) books on graph theory, "path" means "simple path"; a path may not repeat edges or vertices. If you are going to use some unusual terminology, you need to tell us about it, so we will know what you're talking about. So your "paths" do not have to be simple. However, if you allowed vertices and edges to be repeated, then one long "path" would do the job. So I guess your "path" is allowed to repeat vertices but not edges. In graph theory, a walk which may repeat vertices but may not repeat edges is usually called a trail. Let me restate your question:




          What is the minimum number of edge-disjoint trails covering all the edges of the complete bipartite graph $K_{7,10}$?




          The answer (five) follows from a well known extension of the characterization of Eulerian graphs:



          Theorem. Let $k$ be a positive integer. Suppose a (finite) connected graph $G$ has exactly $2k$ vertices of odd degree. Then the edges of $G$ can be covered by $k$ (and no fewer) edge-disjoint trails.



          Proof. You can't do with fewer than $k$ trails, since each of the $2k$ odd degree vertices must be an endpoint of a trail. (You gave this argument in your question.) to see that $k$ trails suffice, add $k$ new edges to the graph, joining the odd-degree vertices in pairs. The resulting graph (which may have multiple edges, but that's O.K.) is connected, and has no vertices of odd degree. Therefore the new graph is Eulerian, meaning that it contains a circuit (i.e. a closed trail) which traverses each edge exactly once. When we remove the $k$ extra edges (to get back to the original graph), the circuit break up into $k$ trails, each of which connects a pair of odd-degree vertices.



          Your graph $K_{7,10}$ is connected and has $10$ vertices of odd degree, so it can be covered by $5$ edge-disjoint trails. If you want to construct a set of $5$ trails that works, I recommend using Hierholzer's algorithm to find an Euler circuit in the enlarged graph.






          share|cite|improve this answer









          $endgroup$



          Let's start by clarifying the problem statement.



          In the title, and again in the first line of the question, you say you want a set that "contains all the paths" but it's clear that you don't mean that; what you want is a set of paths containing all the edges.



          In a comment you say the paths don't have to be "simple paths". In most (not all) books on graph theory, "path" means "simple path"; a path may not repeat edges or vertices. If you are going to use some unusual terminology, you need to tell us about it, so we will know what you're talking about. So your "paths" do not have to be simple. However, if you allowed vertices and edges to be repeated, then one long "path" would do the job. So I guess your "path" is allowed to repeat vertices but not edges. In graph theory, a walk which may repeat vertices but may not repeat edges is usually called a trail. Let me restate your question:




          What is the minimum number of edge-disjoint trails covering all the edges of the complete bipartite graph $K_{7,10}$?




          The answer (five) follows from a well known extension of the characterization of Eulerian graphs:



          Theorem. Let $k$ be a positive integer. Suppose a (finite) connected graph $G$ has exactly $2k$ vertices of odd degree. Then the edges of $G$ can be covered by $k$ (and no fewer) edge-disjoint trails.



          Proof. You can't do with fewer than $k$ trails, since each of the $2k$ odd degree vertices must be an endpoint of a trail. (You gave this argument in your question.) to see that $k$ trails suffice, add $k$ new edges to the graph, joining the odd-degree vertices in pairs. The resulting graph (which may have multiple edges, but that's O.K.) is connected, and has no vertices of odd degree. Therefore the new graph is Eulerian, meaning that it contains a circuit (i.e. a closed trail) which traverses each edge exactly once. When we remove the $k$ extra edges (to get back to the original graph), the circuit break up into $k$ trails, each of which connects a pair of odd-degree vertices.



          Your graph $K_{7,10}$ is connected and has $10$ vertices of odd degree, so it can be covered by $5$ edge-disjoint trails. If you want to construct a set of $5$ trails that works, I recommend using Hierholzer's algorithm to find an Euler circuit in the enlarged graph.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Jan 12 at 8:25









          bofbof

          52.4k558121




          52.4k558121












          • $begingroup$
            That's awsome! Sorry for the bad terminology I don't study in English, you got that right.
            $endgroup$
            – MercyDude
            Jan 12 at 8:49










          • $begingroup$
            Btw, why adding only one extra vertex won't suffice ? adding one vertex and connecting it to each of the 10 vertices will upgrade their degree to an even one and therefore I can construct an Euler circuit, though I'm not sure how exactly.
            $endgroup$
            – MercyDude
            Jan 12 at 15:34










          • $begingroup$
            @MercyDude That will work too. Not sure why adding one vertex and $10$ edges is better than adding no vertex and $5$ edges. Did you read the Wikipedia page about constructing a circuit? The point is, if you've got a circuit that doesn't use all the edges, you can enlarge it by patching in another circuit. "Rinse and repeat."
            $endgroup$
            – bof
            Jan 12 at 15:47


















          • $begingroup$
            That's awsome! Sorry for the bad terminology I don't study in English, you got that right.
            $endgroup$
            – MercyDude
            Jan 12 at 8:49










          • $begingroup$
            Btw, why adding only one extra vertex won't suffice ? adding one vertex and connecting it to each of the 10 vertices will upgrade their degree to an even one and therefore I can construct an Euler circuit, though I'm not sure how exactly.
            $endgroup$
            – MercyDude
            Jan 12 at 15:34










          • $begingroup$
            @MercyDude That will work too. Not sure why adding one vertex and $10$ edges is better than adding no vertex and $5$ edges. Did you read the Wikipedia page about constructing a circuit? The point is, if you've got a circuit that doesn't use all the edges, you can enlarge it by patching in another circuit. "Rinse and repeat."
            $endgroup$
            – bof
            Jan 12 at 15:47
















          $begingroup$
          That's awsome! Sorry for the bad terminology I don't study in English, you got that right.
          $endgroup$
          – MercyDude
          Jan 12 at 8:49




          $begingroup$
          That's awsome! Sorry for the bad terminology I don't study in English, you got that right.
          $endgroup$
          – MercyDude
          Jan 12 at 8:49












          $begingroup$
          Btw, why adding only one extra vertex won't suffice ? adding one vertex and connecting it to each of the 10 vertices will upgrade their degree to an even one and therefore I can construct an Euler circuit, though I'm not sure how exactly.
          $endgroup$
          – MercyDude
          Jan 12 at 15:34




          $begingroup$
          Btw, why adding only one extra vertex won't suffice ? adding one vertex and connecting it to each of the 10 vertices will upgrade their degree to an even one and therefore I can construct an Euler circuit, though I'm not sure how exactly.
          $endgroup$
          – MercyDude
          Jan 12 at 15:34












          $begingroup$
          @MercyDude That will work too. Not sure why adding one vertex and $10$ edges is better than adding no vertex and $5$ edges. Did you read the Wikipedia page about constructing a circuit? The point is, if you've got a circuit that doesn't use all the edges, you can enlarge it by patching in another circuit. "Rinse and repeat."
          $endgroup$
          – bof
          Jan 12 at 15:47




          $begingroup$
          @MercyDude That will work too. Not sure why adding one vertex and $10$ edges is better than adding no vertex and $5$ edges. Did you read the Wikipedia page about constructing a circuit? The point is, if you've got a circuit that doesn't use all the edges, you can enlarge it by patching in another circuit. "Rinse and repeat."
          $endgroup$
          – bof
          Jan 12 at 15:47











          0












          $begingroup$

          Every path in $K_{7,10}$ goes through at most $15$ points, since at least half of the vertices rounded down are in the part of size $7$. This means each path covers at most $14$ edges. Since $K_{7,10}$ has $70$ edges, it will take at least $70/14=5$ paths to include every edge of $K_{7,10}$.



          To show that $5$ is optimal, it suffices to list out $5$ paths which include each edge of $K_{7,10}$ exactly once. Here they are; one part is labeled with the digits $0$ to $9$, the other with letters $A$ to $G$.



          0 1 2 3 4 5 6 7
          |/|/|/|/|/|/|/
          A B C D E F G

          2 3 4 5 6 7 8 9
          |/|/|/|/|/|/|/
          A B C D E F G

          4 5 6 7 8 9 0 1
          |/|/|/|/|/|/|/
          A B C D E F G

          6 7 8 9 0 1 2 3
          |/|/|/|/|/|/|/
          A B C D E F G

          8 9 0 1 2 3 4 5
          |/|/|/|/|/|/|/
          A B C D E F G





          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Thanks, but why "Every path in K7,10 goes through at most 15 points" For example in your first path I can connect 7 to A (It doesn't have to be a simple path...)
            $endgroup$
            – MercyDude
            Jan 12 at 0:30






          • 2




            $begingroup$
            Gotcha, then my proof does not work. The proof in your post about the vertices in the 10 part having odd degree is correct, and proves the minimum possible cardinality is at least 5. The construction in my post proves the minimum is at most 5, so together you know the answer is 5.
            $endgroup$
            – Mike Earnest
            Jan 12 at 1:09
















          0












          $begingroup$

          Every path in $K_{7,10}$ goes through at most $15$ points, since at least half of the vertices rounded down are in the part of size $7$. This means each path covers at most $14$ edges. Since $K_{7,10}$ has $70$ edges, it will take at least $70/14=5$ paths to include every edge of $K_{7,10}$.



          To show that $5$ is optimal, it suffices to list out $5$ paths which include each edge of $K_{7,10}$ exactly once. Here they are; one part is labeled with the digits $0$ to $9$, the other with letters $A$ to $G$.



          0 1 2 3 4 5 6 7
          |/|/|/|/|/|/|/
          A B C D E F G

          2 3 4 5 6 7 8 9
          |/|/|/|/|/|/|/
          A B C D E F G

          4 5 6 7 8 9 0 1
          |/|/|/|/|/|/|/
          A B C D E F G

          6 7 8 9 0 1 2 3
          |/|/|/|/|/|/|/
          A B C D E F G

          8 9 0 1 2 3 4 5
          |/|/|/|/|/|/|/
          A B C D E F G





          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Thanks, but why "Every path in K7,10 goes through at most 15 points" For example in your first path I can connect 7 to A (It doesn't have to be a simple path...)
            $endgroup$
            – MercyDude
            Jan 12 at 0:30






          • 2




            $begingroup$
            Gotcha, then my proof does not work. The proof in your post about the vertices in the 10 part having odd degree is correct, and proves the minimum possible cardinality is at least 5. The construction in my post proves the minimum is at most 5, so together you know the answer is 5.
            $endgroup$
            – Mike Earnest
            Jan 12 at 1:09














          0












          0








          0





          $begingroup$

          Every path in $K_{7,10}$ goes through at most $15$ points, since at least half of the vertices rounded down are in the part of size $7$. This means each path covers at most $14$ edges. Since $K_{7,10}$ has $70$ edges, it will take at least $70/14=5$ paths to include every edge of $K_{7,10}$.



          To show that $5$ is optimal, it suffices to list out $5$ paths which include each edge of $K_{7,10}$ exactly once. Here they are; one part is labeled with the digits $0$ to $9$, the other with letters $A$ to $G$.



          0 1 2 3 4 5 6 7
          |/|/|/|/|/|/|/
          A B C D E F G

          2 3 4 5 6 7 8 9
          |/|/|/|/|/|/|/
          A B C D E F G

          4 5 6 7 8 9 0 1
          |/|/|/|/|/|/|/
          A B C D E F G

          6 7 8 9 0 1 2 3
          |/|/|/|/|/|/|/
          A B C D E F G

          8 9 0 1 2 3 4 5
          |/|/|/|/|/|/|/
          A B C D E F G





          share|cite|improve this answer









          $endgroup$



          Every path in $K_{7,10}$ goes through at most $15$ points, since at least half of the vertices rounded down are in the part of size $7$. This means each path covers at most $14$ edges. Since $K_{7,10}$ has $70$ edges, it will take at least $70/14=5$ paths to include every edge of $K_{7,10}$.



          To show that $5$ is optimal, it suffices to list out $5$ paths which include each edge of $K_{7,10}$ exactly once. Here they are; one part is labeled with the digits $0$ to $9$, the other with letters $A$ to $G$.



          0 1 2 3 4 5 6 7
          |/|/|/|/|/|/|/
          A B C D E F G

          2 3 4 5 6 7 8 9
          |/|/|/|/|/|/|/
          A B C D E F G

          4 5 6 7 8 9 0 1
          |/|/|/|/|/|/|/
          A B C D E F G

          6 7 8 9 0 1 2 3
          |/|/|/|/|/|/|/
          A B C D E F G

          8 9 0 1 2 3 4 5
          |/|/|/|/|/|/|/
          A B C D E F G






          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Jan 12 at 0:14









          Mike EarnestMike Earnest

          24.3k22151




          24.3k22151












          • $begingroup$
            Thanks, but why "Every path in K7,10 goes through at most 15 points" For example in your first path I can connect 7 to A (It doesn't have to be a simple path...)
            $endgroup$
            – MercyDude
            Jan 12 at 0:30






          • 2




            $begingroup$
            Gotcha, then my proof does not work. The proof in your post about the vertices in the 10 part having odd degree is correct, and proves the minimum possible cardinality is at least 5. The construction in my post proves the minimum is at most 5, so together you know the answer is 5.
            $endgroup$
            – Mike Earnest
            Jan 12 at 1:09


















          • $begingroup$
            Thanks, but why "Every path in K7,10 goes through at most 15 points" For example in your first path I can connect 7 to A (It doesn't have to be a simple path...)
            $endgroup$
            – MercyDude
            Jan 12 at 0:30






          • 2




            $begingroup$
            Gotcha, then my proof does not work. The proof in your post about the vertices in the 10 part having odd degree is correct, and proves the minimum possible cardinality is at least 5. The construction in my post proves the minimum is at most 5, so together you know the answer is 5.
            $endgroup$
            – Mike Earnest
            Jan 12 at 1:09
















          $begingroup$
          Thanks, but why "Every path in K7,10 goes through at most 15 points" For example in your first path I can connect 7 to A (It doesn't have to be a simple path...)
          $endgroup$
          – MercyDude
          Jan 12 at 0:30




          $begingroup$
          Thanks, but why "Every path in K7,10 goes through at most 15 points" For example in your first path I can connect 7 to A (It doesn't have to be a simple path...)
          $endgroup$
          – MercyDude
          Jan 12 at 0:30




          2




          2




          $begingroup$
          Gotcha, then my proof does not work. The proof in your post about the vertices in the 10 part having odd degree is correct, and proves the minimum possible cardinality is at least 5. The construction in my post proves the minimum is at most 5, so together you know the answer is 5.
          $endgroup$
          – Mike Earnest
          Jan 12 at 1:09




          $begingroup$
          Gotcha, then my proof does not work. The proof in your post about the vertices in the 10 part having odd degree is correct, and proves the minimum possible cardinality is at least 5. The construction in my post proves the minimum is at most 5, so together you know the answer is 5.
          $endgroup$
          – Mike Earnest
          Jan 12 at 1:09


















          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%2f3070412%2fminimum-cardinal-number-of-a-set-contains-all-the-paths-of-a-complete-bi-partite%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

          Human spaceflight

          Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

          張江高科駅