Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

1 Answer

up vote 4 down vote accepted

HINTS:

  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|improve this answer
    
@entreband: You’ve got it: that’s exactly right. –  Brian M. Scott Nov 5 '12 at 7:53
add comment

Your Answer

 
discard

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.