1
$\begingroup$

Could someone give a precise definition of what 'edge disjoint union' means in graph theory? i.e. what does it mean to say a graph $G$ can be written as the edge disjoint union of graphs $H$, $K$?

I've been trying to look for a precise definition and annoyingly cannot find one.

Is it just a matter of $e(H)\sqcup e(K)=e(G)$? Or do we require the graph $H\cup K$ include all the vertices of $G$ as well (e.g. in the case that $G$ has isolated vertices with no edges which may not appear in $H,K$)

$\endgroup$
1
  • 3
    $\begingroup$ It means $G = H \cup K$ and $e(H) \cap e(K) = \emptyset$, so yes you do need to get all of the vertices in $G$ as well. $\endgroup$ Nov 25 '20 at 14:46
1
$\begingroup$

If we say $G$ can be written as the edge disjoint union of graphs $H$ and $K$, first of all, this means $V(G) = V(H) \cup V(K)$ because otherwise we couldn't have the graph $G$ right? And as you suggested, we must have $E(H)\sqcup E(K)=E(G)$ as disjoint union.

In this way, we also cover the isolated vertices case you mentioned as there are no edges incident to those vertices at all. So, we can put those vertices to both $V(H)$ and $V(K)$ as well without having any trouble, as long as they are contained in $V(H) \cup V(K)$.

$\endgroup$

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.