Bee_see one year ago Draw all non-isomorphic trees on 4 vertices. There are only 2 of them.

1. Bee_see

2. Bee_see

I don't understand the text for how to find the non-isomorphic trees for n vertices.

3. beginnersmind

Do you feel like you have a good handle on what it means for two graphs to be isomorphic? I don't mean reciting the definition, but looking at two graphs and telling if they are isomorphic or not?

4. Bee_see

I know there are some things that make two graphs isomorphic...same degree sequence, if they are connected, same number of vertices and edges, and the labeling.

5. beginnersmind

Isomorphic graphs are basically the same with the labels of the vertices rearranged. E.g:|dw:1441339530967:dw| So anyway, if you look at that tree on 3 vertices, you can see that there are two types of vertices. The middle and the end. This gives you a hint of how you can connect the 4th vertex.

6. Bee_see

why can't the graphs for 3 vertices be drawn like..|dw:1441339802826:dw|? why only straight?

7. beginnersmind

They could, but it would make no difference. They would still be the same graphs.

8. beginnersmind

All that matters is which vertices are connected through which edges.

9. Bee_see

how are they the same graph?

10. beginnersmind

A graph is a list of verticies and a list of edges. Something like this: Vertices: A, B, C Edges: A connected to B B connected to C You can draw these graphs in various ways. Here's 3 drawings all representing the same graph: |dw:1441340182327:dw|

11. Bee_see

ok

12. beginnersmind

So yeah, graphs are lists of vertices and edges (with the two end-vertices included). Trees are graphs where you can't go around a circle. Isomorphism is kind of hard to describe in a few lines but if 2 graphs look the same with the names of the vertices removed then they are isomorphic.

13. beginnersmind

E.g. |dw:1441340605627:dw| No matter how I try to relabel the vertices of (1), I won't get (2). They are fundamentally different.

14. beginnersmind

Here's an example with trees|dw:1441340784337:dw| Can you guess if these two are isomorphic?

15. Bee_see

I guess they are isomorphic...But I'm just guessing...

16. Bee_see

you did write to pay attention to the middle and last vertex in the graph with 3 vertices...I see that you added vertices in this different spots..

17. Bee_see

these*

18. beginnersmind

Yes, and that's an important difference. Note that the left hand side one vertex is connected to 3 edges. On the right 2 edges is the maximum. I can't change that by shuffling around the names of the vertices.

19. beginnersmind

I'm going to list the edges for both: On the left hand side we have: L_E = {(A,B) , (B,C) , (B,D)} On the right hand side: R_E = {(A,B) , (B,C) , (C,D)} The question is can I change around the labels so that I get the same pairs for both? An isomorphism of L_E would be to take all vertices and change them to something else. For example A->B, B->C, C->D, D->A The list of edges after our isomorphic transformation would look like this: L_E* = {(B,C) , (C,D) , (C,A)} or graphically |dw:1441341810154:dw|

20. beginnersmind

By the left and right I mean the graphs in the earlier post|dw:1441341985270:dw|

21. beginnersmind

Anyway, this is getting somewhat long and I'm not sure this is the best format to explain graphs :) I suggest rereading the text, to try to clear up some confusions.

22. Bee_see

That's fine. I will re-read the text.

23. beginnersmind

good luck

24. zzr0ck3r

They are isomorphic if there is a bijection $$\alpha$$ between the sets of vertices such that if $$u$$ is adjacent to $$v$$ then $$\alpha(u)$$ is adjacent to $$\alpha(v)$$. I am assuming we mean simple graphs, else the definition is a little more technical, but says the same thing.