How can we draw all the non-isomorphic graphs on $4$ vertices ? But it is mentioned that $ 11 $ graphs are possible.
$\endgroup$4 Answers
$\begingroup$Just mentioning a couple of links you might find useful to answer similar questions.
$\endgroup$ $\begingroup$Start by drawing the 4 vertices. Then draw all the possible graphs with 0 edges (there is only one). Next, draw all the possible graphs with 1 edge (again, there is only one). Continue until you draw the complete graph on 4 vertices. You should end up with 11 graphs.
$\endgroup$ 2 $\begingroup$Label the vertices $1,2,3,4$.
There are $11$ non-Isomorphic graphs.
With $0$ edges only $1$ graph
with $1$ edges only $1$ graph: e.g $(1,2)$ from $1$ to $2$
With $2$ edges $2$ graphs: e.g $(1,2)$ and $(2,3)$ or $(1,2)$ and $(3,4)$
With $3$ edges $3$ graphs: e.g $(1,2),(2,4)$ and $(2,3)$ or $(1,2),(2,3)$ and $(1,3)$ or $(1,2),(2,3)$ and $(3,4)$
with $4$ edges $2$ graphs: e.g $(1,2),(2,3),(3,4)$ and $(1,4)$ or $(1,2),(2,3),(1,3)$ and $(2,4)$
With $5$ edges only $1$ graph: $(1,2),(2,3),(3,4),(1,4)$ and $(1,3)$
With $6$ edges only $1$ graph: $(1,2),(2,3),(3,4),(1,4),(1,3)$ and $(2,4)$
All those non-isomorphic graphs are $1+1+2+3+2+1+1=11$
$\endgroup$ 1 $\begingroup$How many non-isomorphic graphs can you draw with $4$ vertices and $0$ edges? How many with $1$ edge? $2$? $\dots$
$\endgroup$ 2
