# Find the number of edges

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?

• 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. – LSpice Jun 3 '19 at 18:12
• 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)$. – LSpice Jun 3 '19 at 18:20
• @LSpice you are right. Disjoin condition is common to both parts, but i am not really sure wether this condition should be used. – 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$$.
• 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? – gete Jun 3 '19 at 20:00
• 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. – gete Jun 3 '19 at 20:26