0
$\begingroup$

There are $6$ points in the plane such that each point is connected to exactly $3$ distinct points. Find the number of all possible pairs. Example : If the points are $\{1,2,3,4,5,6\}$ such that $1$ is connected to $2,3,4$ then, $2,3,4$ will already be connected to $1$, so, you have to find the other two choices for these three numbers. And so on. We have to find all possible $(a,b)$ where $a,b$ represent the connected points like $(1,2), (1,3), \cdots$. Note that $(1,2)$ and $(2,1)$ will be same.

My take on the part : I think Principle of Inclusion-Exclusion will be appropriate here but cannot think of a solution using that. Also, by finding all possible choices for a pair $(a,b)$ seems hard. I did a brute force calculation and it seems to be $9$ pairs.

$\endgroup$
1
$\begingroup$

You are overthinking it. Every point is connected to $3$ points, so we have $6\cdot 3=18$ pairs, but we've counted each pair twice, so there are only $9$.

$\endgroup$
  • $\begingroup$ Oops, yes. Thank you! $\endgroup$ – Mathejunior Apr 18 '18 at 2:29

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.