I Have the following question :

Give three examples of simple, connected graphs, all with 8 vertices with degrees 2, 2, 2, 2, 3, 3, 4 and 4, no pairs of which are isomorphic

What is the best method to find such 3 graphs ? In general how can I proceed to find 2 or more non isomorphic Graphs that have the same numer of vertices with the same degree?

Thank you !


Hints: Each graph has two vertices of degree 4. Call them $a$ and $b$.

  1. A graph where $a$ and $b$ share an edge cannot be isomorphic to a graph where $a$ and $b$ do not share an edge.

  2. A graph where both of $a$ or $b$ share an edge with a vertex of order 3 is not isomorphic to a graph where only one does.

  3. A graph where one of $a$ or $b$ is adjacent to all of the vertices of order 2 is not isomorphic to a graph where neither one is, or to a graph where both are.

  4. Etc.

  • $\begingroup$ thank you , do you know any method for solving this in general ? for example with this variation : Give four examples of simple, connected graphs, all with 8 vertices with degrees 2, 2, 2, 2, 3, 3, 4 and 4 $\endgroup$ Apr 29 '14 at 18:53
  • $\begingroup$ You didn't understand my answer, did you? $\endgroup$
    – MJD
    Apr 29 '14 at 18:55
  • $\begingroup$ yes I did, sorry i put the same example in my edit . can you recommend a more general approach to this problem ? $\endgroup$ Apr 29 '14 at 19:01
  • $\begingroup$ @user2505650 This is the general approach, MJD finds the conditions which would make graphs non-isomorphic. You have to do the same and then draw out a graph according to each condition. $\endgroup$
    – stackErr
    Apr 29 '14 at 19:19

In general, you can define 0/1 variables $a_{ij}$ that say whether edge $(i,j)$ is in the graph, and code up the constraints on the degrees by saying that $\sum_j a_{ij} = deg(i)$ where $deg(i)$ is the degree of the $i$th vertex. This system of equations and inequalities gives you a polytope and the integer value points inside the polytope correspond to the graphs you can make that satisfy the vertex degree requirements. Then for each graph you can permute the vertices that have the same degree to get all isomorphic graphs, and the total number of equivalence classes you get is the total number of non-isomorphic graphs you can make. There is literature on listing integer points inside of polytopes if you're interested in this computational approach. However when you have many vertices that have the same degree, you'll get many isomorphic graphs so this approach is only viable when the number of vertices of each degree is relatively low (e.g. one vertex for most degrees) and/or the total number of vertices is not too large. But it should work for 8 vertices just fine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.