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

- Bee_see

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

- chestercat

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga.
Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus.
Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.

Get this expert

answer on brainly

SEE EXPERT ANSWER

Get your **free** account and access **expert** answers to this

and **thousands** of other questions

- Bee_see

##### 1 Attachment

- Bee_see

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

- 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?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- 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.

- 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.

- Bee_see

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

- beginnersmind

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

- beginnersmind

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

- Bee_see

how are they the same graph?

- 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|

- Bee_see

ok

- 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.

- 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.

- beginnersmind

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

- Bee_see

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

- 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..

- Bee_see

these*

- 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.

- 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|

- beginnersmind

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

- 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.

- Bee_see

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

- beginnersmind

good luck

- 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.

Looking for something else?

Not the answer you are looking for? Search for more explanations.