A simple problem of graph theory.

Question

There are how many $4$ vertices connected graphs not including a triangle?

My try:I made 3 such graphs.Is it maximum possible number of such graphs or there are many others?Is there any formula in graph theory to calculate this?

Answer 1

As you've seen in the other comments, there are just three - the 4-cycle, 3-star and the linear tree on 4 vertices. We can prove these are the only connected triangle free simple graphs on 4 vertices by noting that if a graph is bipartite then it contains no triangles (or any cycles of odd length). Therefore if we find all connected bipartite graphs on 4 vertices we've found all triangle-free ones too.

You can either divide four vertices into two sets of 2 vertices $\left\{1,2\right\},\left\{3,4\right\}$ or a set of 1 vertex $\left\{1\right\}$ and a set of 3 vertices $\left\{2,3,4\right\}$. In the first case, since the graph is connected WLOG you must connect at least $1\sim3$, $3\sim 2$ and $2\sim4$. This gives the linear tree on four vertices. You can also connect $1\sim4$ to get the 4-cycle.

In the second case, to get a connected graph you must connect the single vertex $1$ to each of $2,3$ and $4$, giving the 3-star.