Ace Test Series: Graph Theory - Counting

Question

Number of multi-graphs possible with 4 vertices and at most 2 edges between each pair of vertices is ________________

Comments

Yes, it should be 729. Previously, I thought it is "at most 2 edges in the multigraph."

---

is it 665 ?

---

There will be ⁴C₂ = 6 possible ways to select a pair of vertices from 4 vertices. And between every pair there will be 0,1 or 2 vertices. Hence, for 6 pairs 3⁶ = 729 possible combinations. Therefore, the answer is 729.

Answer 1

But why we are not subtracting no. of simple graphs from 729 i.e shouldn’t answer be like 729-(no.of simple graphs)=665.