1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 one or two

  • 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.