Understanding Graph Theory: Exploring K6 and Multidesign Problems

[nickadams]

Hi I was reading a project description for a graph theory REU and I got stuck on a sentence I couldn't understand.

Here is the description and I've bolded the part I don't get.

Consider n dots placed in a circle. These dots are called vertices. Then, if each dot is connected to every other dot by lines (or edges), we have the complete graph on n vertices. We call it Kn. In this project, we will study K6 and look at three subgraphs of K6 which, when taken together, make up K6 in its entirety. In other words, we would write that there are three distinct graphs, G1, G2, G3 such that G1 U G2 U G3 = K6. Given such a triple, (G1, G2, G3), the multidesign problem is to take another graph and partition it into copies of the triple using at least one of each triple.

Does this mean to remove vertices from the "other graph" until you've broken it up to G1, G2, and G3 (and maybe some other stuff in addition)?


Thanks

 

[homeomorphic]

It's a little confusing. It's not clear what they mean by union. You would assume it's union of the edges and union of the vertices. It's not clear whether the subgraphs are supposed to be disjoint. Usually partitioning a set means breaking it up into a disjoint union. That's confusing in the context of graphs because it would seem to mean that the graph can be broken up into disconnected pieces, which is obviously not the case for K6. You wouldn't remove any vertices because the union is supposed to be the whole thing. So, I'm confused, too. But I wanted to point out that it is pretty confusingly written. If I were you, I would just skip it and try to see what it might mean by reading ahead and seeing how it's used.