graph theory
How many distinct connected graphs (up to isomorphism) are there on 4 vertices which do not contain a $K_3$ subgraph?
I think the answer is 3? Because there are 2 non-isomorphic trees on 4 unlabeled vertices plus one shaped like a quadrilateral. Any help would be appreciated!
Here is an example of two non-isomorphic graphs that are at distance $0$ by your definition:
Both graphs have $6$ vertices, all of degree $3$. But the left one is $K_{3,3}$, a bipartite graph; the right one is not bipartite because, in particular, it has two clearly visible triangles. This is one way to see that they're not isomorphic. (You can also look at their complements; the complement of the right graph is connected and the complement of the left graph isn't.)
In general, for large $k$ and $n$, if there are any $k$-regular graphs on $n$ vertices, there are lots.
One measure I might suggest is "edit distance" between two graphs: the number of times you need to perform some well-defined operation (for example, adding or removing an edge or an isolated vertex) to turn one graph into something isomorphic to the other.
This is a very common situation in enumeration problems. When we count some mathematical objects do we want to regard isomorphic objects are being essentially the same or not? We say that two graphs that are isomorphic are equal up to isomorphism. This is also known as choosing unlabeled versus labeled objects. Here is a quote from MathWorld:
A graph in which individual nodes have no distinct identifications except through their interconnectivity. Graphs in which labels (which are most commonly numbers) are assigned to nodes are called labeled graphs. Unless indicated otherwise by context, the unmodified term "graph" generally refers to an unlabeled graph.
Thus, in a labeled simple graph with $N$ vertices, each of the $\frac{N(N-1)}2$ edges can be in the graph or not independently. This implies the simple expression $2^{\frac{N(N-1)}2}$ for the number of labeled graphs. For unlabeled graphs the expression is more complicated as in OEIS sequence A000088.
Best Answer
Yes you're correct. First, if the graph contains a cycle, it must be a 4-cycle - otherwise it would absolutely contain a triangle. Then, since it is connected, any other graph must be a tree; which as you pointed out can only be one of two possibilities.