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$– LSpiceJun 3, 2019 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$– LSpiceJun 3, 2019 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$– geteJun 3, 2019 at 19:44
1 Answer
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$.

$\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$– geteJun 3, 2019 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$– geteJun 3, 2019 at 20:26

$\begingroup$ You are right that I failed to consider those edges. I have edited my answer accordingly. $\endgroup$ Jun 3, 2019 at 20:49