Number of edges in a union of two graphs

Question

Suppose $G=(V, E)$ and $G'=(V', E')$ are two graphs having number of edges as $|E|$ and $|E'|$, respectively, where $E$ and $E'$ are set of edges in $G$ and $G'$, respectively. Then the number of edges in $G\cup G'$ is $|E|+|E'|-|E\cap E'|$. Is this claim true? Please suggest me. Note. This is important to me as i am trying to formulate and estimate the number of edges in a graph formed by two or more components under certain binary operations like $\cup$, $\cap$ etc. For instance, what would be the number of edges in $G\cap(G'\cup G'')$, where number of vertices in $G, G'$ and $ G''$ are known and so on.

Answer 1

Well, let's be careful. If $G$ and $G'$ are the graphs $(V,E)$ and $(V,E')$, respectively, then the union graph $G \cup G'$ is defined to be $(V, E \cup E')$. The number of edges in this graph is of course $|E \cup E'|$, which equals $|E| + |E'| - |E \cap E'|$, because this equation holds for any two subsets. So, this is true.

But your question asks: If the number of edges in $G$ and $G'$ are $|E|$ and $|E'|$ respectively, then is the number of edges in $G \cup G'$ equal to $|E| + |E'| - |E \cap E'|$? Here's a counterexample: Take $V = \{a,b,c\}$, and suppose $G$ and $G'$ have edge sets $\{ab, ac\}$ and $\{ab,bc\}$, respectively. Take $E=E' = \{1,3\}$. Then, it's true that both $G$ and $G'$ have $|E|=2$ and $|E'|=2$ edges, respectively, and $G \cup G'$ has $2+2-1=3$ edges, but $|E|+|E'|-|E \cap E'|=2+2-2=2$, which does not equal $3$.

I know the above counterexample is not what you meant - you meant for $E, E'$ to also be the corresponding edge sets. This counterexample illustrates one needs to communicate logically rigorously, otherwise the statements you intended to be true could be false.

Answer 2

Yes it is correct. It is just inclusion-exclusion formula for the sets of edges.

$$|E\cup E' |= |E|+|E'|-|E\cap E'|$$

Answer 3

Your claim is correct (for finite graphs).

You can start with taking naïvely the number of elements of $E$ and sum up the number of elements of $E'$.

But then all elements that belong to both $E$ and $E'$ are counted twice.

This must be repaired by subtracting all elements that belong to $E$ and $E'$.

This is an application of the principle of inclusion/exclusion.

Answer 4

Yes that is true. The edge count of the union follows the inclusion exclusion principle.