Graph Isomorphism: Prove Only 1 Graph w/ Degree Seq (3,3,3,3,4)

In summary, the conversation discusses constructing non-isomorphic graphs from a given degree sequence (3,3,3,3,4). The speaker suggests starting with a W5 graph, which has been identified as the only possible option. The conversation ends with the explanation of how the given degree sequence can be transformed into a W5 graph.
  • #1
Petkovsky
62
0
How many graphs(non isomorphic) can you construct from the degree sequence (3,3,3,3,4). The answer has to be proven of course.

The only one I could find was a W5 graph, but i can't prove that it is the only one. I know that for two graphs to be isomorphic, a bijection has to exist between the two vertex sets, however i don't know where to start from. Any help would be appreciated.
 
Physics news on Phys.org
  • #2
Just try to construct it from the degrees and see that W5 is the only possibility.

Sketch:
Assume we have a graph with degree sequence (3,3,3,3,4).
- Let A be the vertex with degree 4. A is connected to all vertices.
- Let B be some other vertex than A. B has degree 3 and is therefore connected to all vertices but one which we can call C.
- C has degree 3 so is connected to all vertices but one, and since it isn't connected to B we know that it is connected to all but B.
- Let D be some vertex other than A,B,C. D is connected to A, B and C and has degree 3 so it's connected exactly to these.
- Let E be the last vertex. E is connected to A, B, C.

This is isomorphic to W5 which can be seen by sending A to the center of the wheel and sending (B,C,D,E) to the cycle.
 
  • #3
Aha, i see now. Thank you.
 

FAQ: Graph Isomorphism: Prove Only 1 Graph w/ Degree Seq (3,3,3,3,4)

What is graph isomorphism?

Graph isomorphism is the concept of determining whether two graphs are structurally identical or not. In other words, it is a way to understand if two graphs have the same arrangement of vertices and edges.

What does it mean to prove only 1 graph with the degree sequence (3,3,3,3,4)?

This means that there is only one possible graph with the given degree sequence of 3, 3, 3, 3, and 4. In other words, any other graph with this degree sequence would not be considered isomorphic to the given graph.

How do you prove that there is only 1 graph with a specific degree sequence?

The proof involves using the Havel-Hakimi algorithm, which is a step-by-step process of constructing a graph with a given degree sequence. If the algorithm results in a unique graph, then it can be proven that there is only one graph with that particular degree sequence.

What is the importance of graph isomorphism in computer science?

Graph isomorphism is an important concept in computer science as it has applications in various fields such as network analysis, data mining, and computational biology. It helps in identifying patterns and similarities between different graphs, which can be useful in solving complex problems.

Is determining graph isomorphism a difficult problem?

Yes, graph isomorphism is considered a difficult problem in computer science. It falls under the category of NP problems, which means that there is no known efficient algorithm to solve it. However, for special cases such as proving only one graph with a specific degree sequence, there are algorithms that can provide a solution in polynomial time.

Similar threads

Proving a (known isomorphic) graph is isomorphic
Replies
6
Views
2K
Domination number of a graph G
Replies
9
Views
1K
Proving uniqueness of almost irregular graphs with equal degrees for n=2k
Replies
3
Views
2K
Isomorphism is an equivalence relation on groups
Replies
9
Views
8K
Euler circuit in a directed multigraph
Replies
2
Views
5K
Proving a function is an isomorphism
Replies
16
Views
2K
Proving Cut Vertices in Simple Graphs
Replies
2
Views
1K
Abstract Algebra: Bijection, Isomorphism, Symmetric Sets
Replies
2
Views
1K
Rather , isomorphic graphs, planar graph
Replies
3
Views
3K
Proving a function is a bijection and isomorphic
Replies
4
Views
4K

Hot Threads

Recent Insights

Back
Top