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)

$\endgroup$
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.

$\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
$\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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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