Let $\langle V_1, E_1 \rangle, \langle V_2, E_2 \rangle$ and $\langle V_3, E_3\rangle$ be any three undirected simple graphs with $m$, $n$ and $p$ number of edges, respectively such that $E_2$ and $E_3$ have no edge in common. Then what would be the number of edges in $$ \bigl[(E_1\cup E_2)\cup\lbrace (a,b): \text{$a\in V_1$ and $b\in V_2$} \rbrace\bigr]\cap \bigl[(E_1\cup E_3)\cup\lbrace (c,d): \text{$c\in V_1$ and $d\in V_3$}\rbrace\bigr], $$ where the operations $\cup$ and $\cap$ are usual set union and join, respectively? Also, given that $V_2$ and $V_3$ have no vertex in common. Or, how to simplify and formulate $$ \bigl[(E_1\cup E_2)\cup\lbrace (a,b): \text{$a\in V_1$ and $b\in V_2$} \rbrace\bigr]\cap \bigl[(E_1\cup E_3)\cup\lbrace (c,d): \text{$c\in V_1$ and $d\in V_3$} \rbrace\bigr] $$ to put into a more compact form?

  • $\begingroup$ I put your formulæ in display mode; at least for me, they rendered in a really weird way, where the clarification about the meaning of $\cup$ and $\cap$ came in the middle of the formulæ. Feel free to revert if you don't like it. $\endgroup$ – LSpice Jun 3 '19 at 18:12
  • 1
    $\begingroup$ Is the disjointness condition on $V_2$ and $V_3$ a separate question, or part of the same question? Finally, since your graphs are undirected, I think edges should be unordered pairs $\{a, b\}$, not ordered pairs $(a, b)$. $\endgroup$ – LSpice Jun 3 '19 at 18:20
  • $\begingroup$ @LSpice you are right. Disjoin condition is common to both parts, but i am not really sure wether this condition should be used. $\endgroup$ – gete Jun 3 '19 at 19:44

The number of edges is $m$ plus all the possible edges between $V_1 \cap V_2$ and $V_1 \cap V_3$. For the ease of notation, I will define $V_{1,2}$ as the set of all possible edges between $V_1$ and $V_2$, with a similar definition for $V_{1,3}$.

The intersection of unions is equal to the union of the intersections. Therefore, the set of edges described contains $E_1$, since there is an $E_1$ in both terms of the intersection. Any other term intersected with $E_1$ will be a subset of $E_1$ and so is already taken care of. Therefore, we need only consider the intersections of the remaining terms. By assumption, $E_2 \cap E_3$ is empty. The intersection $V_{1,2} \cap V_{1,3}$, will only contain edges between $V_1 \cap V_2$ and $V_1 \cap V_3$. This means the only intersections left to worry about are the intersection between $E_2$ and $V_{1,3}$, and the same with 2 and 3 switched. However the edges in $E_2$ have both endpoints in $V_2$, which is disjoint from $V_3$, and so the intersection is empty. Therefore, the only edges in the intersection are in $E_1$, which has size $m$, or between $V_1 \cap V_2$ and $V_1 \cap V_3$.

| cite | improve this answer | |
  • $\begingroup$ your answer seem to be very close to what i was expecting. I also thought it wiuld would be $m$ but it's not exactly $m$ i need $m+\text{something}$ for my purpose. Could you please revisit as what are the possible additional edges other than $m$ edges? $\endgroup$ – gete Jun 3 '19 at 20:00
  • $\begingroup$ your answer is correct when $V_1, V_2$ and $V_3$ are distinct sets of vertices i e., they have no vertex in common. But when $V_1$ and $V_2$ , and $V_1$ and $V_3$ have some common vetices or, $E_1$ and $E_2$ has $k_1$ number of common edges and $E_1$ and $E_3$ has $k_2$ number of common edges (say) then i need $m+\text{some positive integer}$ number of edges in the defined set of edges for my purpose. $\endgroup$ – gete Jun 3 '19 at 20:26
  • $\begingroup$ You are right that I failed to consider those edges. I have edited my answer accordingly. $\endgroup$ – weux082690 Jun 3 '19 at 20:49

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.