Find 3 different nonisomorphic graphs with 8 vertices that have the degree sequence 2,2,2,2,2,2,2,2. Answer: An 8-cycle, or two 4-cycles, or a 3-cycle and a 5-cycle.

stylaria3y 2022-07-18 Answered
Nonisomorphic graphs Discrete Math
Find 3 different nonisomorphic graphs with 8 vertices that have the degree sequence 2,2,2,2,2,2,2,2. Answer: An 8-cycle, or two 4-cycles, or a 3-cycle and a 5-cycle.
Can someone show me how these three answers were found? I am a little confused with nonisomorphic graphs. I used to think you could just change the name of each vertex because no matter how you rearranged the vertices they would never be able to be rearranged back to their previous form. But then I was wrong and was told that you have to pay attention to adjacency but how? So for this question, how did the person come by these three answers?
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Eve Good
Answered 2022-07-19 Author has 18 answers
Step 1
Changing the names of the vertices results in an isomorphic graph, of course: the isomorphism sends each vertex to itself under its former name.
Two graphs are isomorphic if there's any bijection between vertices which always takes an edge to an edge; in other words, a bijection of the vertices that preserves adjacency, as you mentioned. It means that it's possible to draw the two graphs the same way.
For instance, on a given set of eight vertices, there are going to be ( 8 5 ) 4 ! 2 = 672 different graphs consisting of a 5-cycle and a 3-cycle; but all of them are isomorphic. Suppose G and H are two such graphs. Say the vertices on the 5-cycle in G, in cyclic order, are v 1 , v 2 , v 3 , v 4 , v 5 , and the vertices on its 3-cycle are v 6 , v 7 , v 8 , while the vertices in H are w 1 , w 2 , w 3 , w 4 , w 5 on the 5-cycle and w 1 , w 2 , w 3 on the 3-cycle. Then mapping v i w i is an isomorphism.
Step 2
Coming to these three kinds of 2-regular 8-vertex graphs isn't too hard, if you know this fact:
If every vertex has degree two, then the graph consists of disjoint cycles (or infinite chains.)So, how can you possibly break 8 vertices into cycles? It seems that the definition you use for "graph" doesn't allow multiple edges or loops, so that a cycle must have at least three vertices.
Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

asked 2021-08-18
Discrete Mathematics Basics
1) Determine whether the relation R on the set of all Web pages is reflexive, symmetric, antisymmetric, and/or transitive, where (a,b)R if and only if
I) everyone who has visited Web page a has also visited Web page b.
II) there are no common links found on both Web page a and Web page b.
III) there is at least one common link on Web page a and Web page b.
asked 2021-08-02
Suppose that A is the set of sophomores at your school and B is the set of students in discrete mathematics at your school. Express each of these sets in terms of A and B.
a) the set of sophomores taking discrete mathematics in your school
b) the set of sophomores at your school who are not taking discrete mathematics
c) the set of students at your school who either are sophomores or are taking discrete mathematics
Use these symbols:
asked 2020-11-09
Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.
asked 2022-04-12
Predicate Logic and Quantifiers
Assume that x y P ( x , y ) is True and that domain of discourse is nonempty. If the statement is true, explain your answer; otherwise, give a counter example.
From the question, we know that x y P ( x , y ) means there is an x for which P(x,y) is true for every y.
So the question wants me to prove y x ¬ P ( x , y ) that it is true, otherwise provide a counter example.
How do i start to answer this question? Do i start by using rules of inferences to proof?
asked 2022-06-20
What to do if the Extended Euclidean Algorithm terminates in one step?
I am trying to solve the linear congruence
14 x 1 ( mod 113 )
So I first find gcd ( 14 , 113 ) = 1. However this means that:
113 = 14 ( 8 ) + 1
There is only one step needed. If I don't have any other equations, how do I find the inverse? Thank you for any help!
asked 2021-08-20
Solve the recursion:
A1=1. A2=1
Ak=5Ak16Ak2

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question