0
$\begingroup$

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.

  • 0
    no, the graph does not need to be connected2012-11-05

1 Answers 1

4

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?
  • 0
    @entreband: You’ve got it: that’s exactly right.2012-11-05