- Background Information:
I am studying discrete mathematics by doing some problems in my textbook. I came across a question that I have a solution for, but I don't understand part of the solution. I need clarification, thanks.
- Original Question: Consider part (a)
- Chegg solution to part (a):
- My Question:
Where is division by 4 coming from? Also, is the equation for the number of edges in complement graph of G or both?
It is the equation for the number of edges in each (i.e. $G$ has $\frac{n(n-1)}{4}$ edges and the complement has $\frac{n(n-1)}{4}$ edges.)
The dividing by four comes from dividing $\frac{n(n-1)}{2}$ by 2. You know that the sum of the number of edges of $G$ and $G$ complement is the number of edges in the complete graph with $n$ vertices: $\frac{n(n-1)}{2}$. So \begin{align}\frac{n(n-1)}{2}&=(\text{edges in G})+\underbrace{(\text{edges in G complement})}_{\text{=edges in G}}\\ &=(\text{edges in G})+(\text{edges in G})\\ &=2(\text{edges in G}),\end{align} and dividing both sides by $2$ yields \begin{align}\frac{\frac{n(n-1)}{2}}{2}=\frac{n(n-1)}{4}=(\text{edges in G})=(\text{edges in G complement}). \end{align}