0
$\begingroup$

I need some help nailing some graph theory terminologies down. I know that a planar graph $G$, is a graph where no two edges intersect one another. A vertex disjoint graph $G1$ is a graph, where $V(G1_1) \ \cap V(G1_2)=\emptyset$, or each sub graph of $G1$ don't share any edges. $K_5$ is a non-planar graph which has $5$ vertices which're connected to one another by edges. However I'm unsure as to what pairwise, vertex disjoint copies of $K_5$ are. It would be great if someone can explain in intuitive English what that is.

$\endgroup$
2
$\begingroup$

Here is one $K_5$: a graph with $5$ vertices (which I've numbered $1$ to $5$), with an edge connecting each pair of vertices.

enter image description here

Here are two vertex-disjoint copies of $K_5$. Ten vertices ($1$ to $10$). The first five form one copy of $K_5$, since each pair of them is connected by an edge. The second five form the other copy of $K_5$, again each pair connected by an edge. They are vertex-disjoint since no vertex in the first five is in the second five.

enter image description here

BTW: your statement about a planar graph is faulty. A planar graph is one that can be drawn so that no two edges cross each other. This is a planar graph, even though there are crossing edges in the picture:

enter image description here

because you can draw it so those edges don't cross:

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So if you wanted to you could make as many vertex disjoint copies of $K_5$ as you wanted, as long as the vertices are different? Also what would pairwise vertex disjoint copies of $K_5$? $\endgroup$ – user686555 Jul 4 '19 at 10:28
  • $\begingroup$ Pairwise vertex disjoint just means each pair of copies are vertex disjoint. $\endgroup$ – Robert Israel Jul 4 '19 at 11:56
  • $\begingroup$ So pairwise vertex disjoint copies just refers to the graph having $x$ many pair copies of $K_5$ such that each copy is vertex disjoint from the others? In this case, if we say that there are $6$ pairwise vertex disjoint copies of $K_5$, then there are $6$ five form graphs and in total $30$ vertices. $\endgroup$ – user686555 Jul 4 '19 at 21:01
  • $\begingroup$ Yes, that's right. $\endgroup$ – Robert Israel Jul 4 '19 at 22:55
  • $\begingroup$ So what's the maximum amount of pairwise vertex disjoint copies of $K_5$ can $G$, $G$ is $5$ planar, have? I know on the minimum side, it's zero because if we have $K_5$ with a vertex $6$ connected to $5$ and a new vertex $7$, where $7$ is connected to $4$ and $5$. If you remove vertex $1$ to $5$ you're just left with vertex $6$ and $7$, which is not a copy of $K_5$. $\endgroup$ – user686555 Jul 4 '19 at 23:16

Your Answer

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