A community for students.
Here's the question you clicked on:
 0 viewing
bahrom7893
 4 years ago
KingGeorge: Determine the number of isomorphism classes of simple 7vertex graphs in which every vertex has degree 4
bahrom7893
 4 years ago
KingGeorge: Determine the number of isomorphism classes of simple 7vertex graphs in which every vertex has degree 4

This Question is Closed

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5http://en.wikipedia.org/wiki/Isomorphism_class this definition doesn't help... lookin thru the textbok

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5textbook definition: An isomorphism class of graphs is an equivalence class of graphs under the isomorphism relation. WTH is an equaivalence class?

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5oh god this is annoying.. im reading the book backwards now lol

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1Informally, an equivalence class is a set of elements that are equivalent to each other under a certain equivalence relation.

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5an equivalence relation in this case is isomorphism right?

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5it passes the 3 conditions for e.r.s

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1remind what e.r.s stands for?

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5equivalence relations lol i just made it up

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1Basically, what this question is asking, is how many 7vertex graphs, where each vertex has degree 4, can be formed such that none of the graphs are isomorphic to each other.

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5no idea how to do that.. honestly.. even if i reread the chapter again.. god i need serious help on this..

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1The way I would approach this, is first by labeling your points {1, 2, ..., 7} and determine some cases to break it up into some small number of things you need to check. After that, I'm a little unsure of how to proceed. Give me a few minutes. I'll keep thinking about it. On a side note, have you ever taken number theory?

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1Just curious since I had a number theory problem assigned for hw a couple weeks ago that the prof. doesn't know how to solve :/ Anyways, I just dug up my old text book that had some graph theory in it. Let's see how helpful it is.

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5I found the solution, will type it out if it helps.. and hopefully u can translate it if u can and are willing to

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5There are exactly two isomorphism classes of 4regular simple graphs with 7 vertices. Simple graphs G and H are isomorphic iff their complements G' and H' are isomorphic, because an isomorphism phi: V(G) > V(H) is also an isomorphism from G' to H' and vice versa.

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5Hence it suffices to count the isomorphism classes of 2regular simple graphs with 7 vertices. Every component of a finite 2regular graph is a cycle. In a simple graph, each cycle has at least 3 vertices. Hence each class is determined by partitioning 7 into integers of size at least 3 to be the sizes of the cycles. The only two graphs that result are C7 and C3+C4  a single cycle or two cycles of length 3 and 4

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1This makes sense to me. Basically, since \(G \cong H \) we know that \( G' \cong H'\) where \(G', H' \) are the complement graphs of \(G\) and \( H\). Thus we only have to count the isomorphism classes of \( G' \) and \(H'\). Make sense so far?

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1Well, since \(G, H\) are 4regular with 7 vertices, their complements are 2regular with 7 vertices. Note that his is a finite 2regular graph, and all connected finite 2regular graphs must be cycles. Also, since it's simple, we need all connected graphs in our complement to have at least 3 points (if it's 1 or 2, we would need a loop, or two paths between the same two points). Still following?

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5does 7 vertices mean 6 edges?

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.17 vertices means there are seven points on the graph.

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5no i know, but would that imply, if all vertices were connected to each other, there would be 6 edges?

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1If every point were to be connected, and there were only 6 edges, it would have to be a giant loop where each vertex has degree 2.

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5hmm then what does 4regular mean? because then u said complements have 2regular so i thought there should be 6 edges in total and 2 of them were missing in the original

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.14regular means that every vertex has 4 edges connected to it. 2regular means every vertex has 2 edges connected.

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5hold on, let me just draw this example real quick

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1As a general rule, if you have a simple nregular graph, and it has m vertices, the complement would be an (mn1)regular graph with m vertices.

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1In other words, if your simple graph has m vertices, and each vertex has degree n, the complement would have m vertices, and each vertex would have degree (mn1).

KingGeorge
 4 years ago
Best ResponseYou've already chosen the best response.1If you were to prove this fact, induction on the degree of the vertices would be the way to do it. Anyways, finishing the original proof; since the components of the the complement graphs must be cycles with at least 3 vertices each, there are only 2 ways to do this. Case 1: You have one cycle with three vertices. Then there are 4 vertices remaining each with degree 2. Thus, those 4 vertices must also be connected in a single cycle, and your graph is C3+C4 (as described above). Case 2: You have a cycle with more that 4 vertices (if it had 4, we would be at case 1 again). Then that cycle must have all 7 vertices so your graph would be C7. Therefore, there only two possible isomorphism classes for the complement of 4regular, 7 vertex graphs. This implies that there are only two isomorphism classes for 4regular, 7 vertex graphs. So we are done. Any questions?

bahrom7893
 4 years ago
Best ResponseYou've already chosen the best response.5nope, thanks, let this just sink in... Thanks a lot man!
Ask your own question
Sign UpFind more explanations on OpenStudy
Your question is ready. Sign up for free to start getting answers.
spraguer
(Moderator)
5
→ View Detailed Profile
is replying to Can someone tell me what button the professor is hitting...
23
 Teamwork 19 Teammate
 Problem Solving 19 Hero
 Engagement 19 Mad Hatter
 You have blocked this person.
 ✔ You're a fan Checking fan status...
Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.