Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can someone please walk me through how to solve this?

Determine the number of graphs on $10$ vertices labeled $1, 2, \cdots, 10$ that contain exactly two out of the following four edges $e_1 = \{1, 2\}$, $e_2 = \{1, 3\}$, $e_3 = \{2, 3\}$, and $e_4 = \{1, 4\}$, and any number of other edges.

share|cite|improve this question
Do you need the graphs connected? – EuYu Nov 5 '12 at 4:43
no, the graph does not need to be connected – entreband Nov 5 '12 at 4:52
up vote 4 down vote accepted


  1. How many edges are possible on $10$ vertices?
  2. How many possible edges are there besides the $4$ edges $e_1,e_2,e_3$, and $e_4$? Call this number $m$.
  3. In how many ways can you choose $2$ of the $4$ edges $e_1,e_2,e_3$, and $e_4$?
  4. In how many ways can you choose an arbitrary subset of the $m$ edges other than these four?
  5. Each of the pairs of edges from $\{e_1,e_2,e_3,e_4\}$ can be combined with any subset of the other $m$ edges; how many different graphs does this produce?
share|cite|improve this answer
@entreband: You’ve got it: that’s exactly right. – Brian M. Scott Nov 5 '12 at 7:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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