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

Question

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)

Answer 1

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.

Answer 2

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