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

  • Thread starter Thread starter Petkovsky
  • Start date Start date
  • Tags Tags
    Graph Isomorphism
Click For Summary
SUMMARY

The discussion centers on proving that the only non-isomorphic graph that can be constructed from the degree sequence (3,3,3,3,4) is the W5 graph. The participants outline a method to demonstrate this by analyzing the connections of vertices based on their degrees. The vertex A, with degree 4, connects to all other vertices, while vertices B, C, D, and E maintain specific connections that lead to the conclusion that W5 is the sole graph fitting the degree sequence.

PREREQUISITES
  • Understanding of graph theory concepts, specifically degree sequences.
  • Familiarity with isomorphic graphs and bijections between vertex sets.
  • Knowledge of the W5 graph structure and its properties.
  • Basic skills in constructing and analyzing graphs from given parameters.
NEXT STEPS
  • Study the properties and applications of the W5 graph in graph theory.
  • Learn about graph isomorphism and techniques for proving non-isomorphism.
  • Explore degree sequences and their implications in graph construction.
  • Investigate other graph types and their degree sequences for comparative analysis.
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in graph construction and isomorphism proofs.

Petkovsky
Messages
61
Reaction score
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
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.
 
Aha, i see now. Thank you.
 

Similar threads

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