# Number of edges in Graph where neighbors are 2-element subsets of {1,…n} with a common element

Let $n\ge2$ be an integer. For the simple graph $G_n$, define the set of nodes as the set of subsets of size 2 from the set {1,2,...n}, where nodes are neighbors iff they have a common element. For example, for $n\ge3$, the nodes {1,2} and {1,3} are neighbors of $G_n$. Find the number of edges for $G_{100}$

I figured to find the number of edges, I should just find the number of 2-element subsets that share a common element. I know the total number of subsets of size 2 should equal $n \choose 2$, but I'm stuck on how to find the number of these subsets that share a common element.

Should I try finding the number of subsets with no common elements and subtract that from $n \choose 2$ or is there a more direct way? Any help/tips would be greatly appreciated.

Your approach is the correct one. For a given vertex (i.e. $2$-element subset) try to figure out how many are its neighbor.
This is the same for each vertex, so it's enough to do this for the node $\{1,2\}$. You could do this directly, and just count the number that have a $1$ and the number that have a $2$: since it has to be a distinct subset (i.e. it can't have both a $1$ and a $2$), it must consist of:
• a number in $\{3,4,\ldots,n\}$.
We have two choices for picking the $1$ or $2$, and $n - 2$ choices for the others. This means each node has degree $2\cdot (n-2)$. To see how this relates to the number of edges, consider what happens when you add up all of the degrees.