Finding Nonisomorphic Graphs: Q&A

[saubbie]

Homework Statement

I have two questions. 1.)There are exactly two nonisomorphic graphs with vertex sequence 3, 3, 3,3, 3, 3, 6. Find them.

2.)Does there exist a connected graph with vertex degrees 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3? If there is, then draw such a graph. If
not, explain why not.

Homework Equations

I am still unclear as to what a nonisomorhpic graph is. I think that I may have found them, but how do I check if they are nonisomorphic?

The Attempt at a Solution

For the second one, my initial thought is that it is not possible since there are 20 vertexes, and each has degree 3 there will always be two that get left with only degree 2. If there were 21 vertexes, then it would be possible. Any other thoughts or suggestions? Thanks.

 

[mighty2000]

Thank you for your questions. I am happy to help you understand nonisomorphic graphs and solve these problems.

A nonisomorphic graph is one that cannot be transformed into another graph by simply relabeling the vertices. In other words, two nonisomorphic graphs have different structures even if they have the same number of vertices and edges.

For your first question, I can confirm that there are indeed two nonisomorphic graphs with the given vertex sequence. To check if they are nonisomorphic, you can compare their structures by looking at the number of edges and the connections between vertices.

For your second question, you are correct in your initial thought. It is not possible to have a connected graph with 20 vertices and all having degree 3. As you mentioned, there will always be two vertices with degree 2. This is because the sum of all vertex degrees in a graph is equal to twice the number of edges. In this case, the sum would be 60, which is an odd number. Since each edge connects two vertices, there must be an even number of edges, making it impossible for all vertices to have degree 3.

I hope this helps clarify the concept of nonisomorphic graphs and solves your problems. If you have any further questions, please don't hesitate to ask. Keep up the good work!