bahrom7893
  • bahrom7893
KingGeorge: Determine the number of isomorphism classes of simple 7-vertex graphs in which every vertex has degree 4
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
chestercat
  • chestercat
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
bahrom7893
  • bahrom7893
http://en.wikipedia.org/wiki/Isomorphism_class this definition doesn't help... lookin thru the textbok
bahrom7893
  • bahrom7893
textbook definition: An isomorphism class of graphs is an equivalence class of graphs under the isomorphism relation. WTH is an equaivalence class?
bahrom7893
  • bahrom7893
oh god this is annoying.. im reading the book backwards now lol

Looking for something else?

Not the answer you are looking for? Search for more explanations.

More answers

KingGeorge
  • KingGeorge
Informally, an equivalence class is a set of elements that are equivalent to each other under a certain equivalence relation.
bahrom7893
  • bahrom7893
an equivalence relation in this case is isomorphism right?
bahrom7893
  • bahrom7893
it passes the 3 conditions for e.r.s
KingGeorge
  • KingGeorge
remind what e.r.s stands for?
bahrom7893
  • bahrom7893
equivalence relations lol i just made it up
KingGeorge
  • KingGeorge
Basically, what this question is asking, is how many 7-vertex graphs, where each vertex has degree 4, can be formed such that none of the graphs are isomorphic to each other.
bahrom7893
  • bahrom7893
no idea how to do that.. honestly.. even if i reread the chapter again.. god i need serious help on this..
KingGeorge
  • KingGeorge
The 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?
bahrom7893
  • bahrom7893
no
KingGeorge
  • KingGeorge
Just 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
  • bahrom7893
oh, thanks :)
bahrom7893
  • bahrom7893
I found the solution, will type it out if it helps.. and hopefully u can translate it if u can and are willing to
bahrom7893
  • bahrom7893
There are exactly two isomorphism classes of 4-regular 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
  • bahrom7893
Hence it suffices to count the isomorphism classes of 2-regular simple graphs with 7 vertices. Every component of a finite 2-regular 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
  • KingGeorge
This 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?
bahrom7893
  • bahrom7893
yes
KingGeorge
  • KingGeorge
Well, since \(G, H\) are 4-regular with 7 vertices, their complements are 2-regular with 7 vertices. Note that his is a finite 2-regular graph, and all connected finite 2-regular 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
  • bahrom7893
does 7 vertices mean 6 edges?
KingGeorge
  • KingGeorge
7 vertices means there are seven points on the graph.
bahrom7893
  • bahrom7893
no i know, but would that imply, if all vertices were connected to each other, there would be 6 edges?
KingGeorge
  • KingGeorge
If 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
  • bahrom7893
hmm then what does 4-regular mean? because then u said complements have 2-regular so i thought there should be 6 edges in total and 2 of them were missing in the original
KingGeorge
  • KingGeorge
4-regular means that every vertex has 4 edges connected to it. 2-regular means every vertex has 2 edges connected.
bahrom7893
  • bahrom7893
hold on, let me just draw this example real quick
bahrom7893
  • bahrom7893
ok continue
KingGeorge
  • KingGeorge
As a general rule, if you have a simple n-regular graph, and it has m vertices, the complement would be an (m-n-1)-regular graph with m vertices.
bahrom7893
  • bahrom7893
ok tnx
KingGeorge
  • KingGeorge
In 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 (m-n-1).
KingGeorge
  • KingGeorge
If 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 4-regular, 7 vertex graphs. This implies that there are only two isomorphism classes for 4-regular, 7 vertex graphs. So we are done. Any questions?
bahrom7893
  • bahrom7893
nope, thanks, let this just sink in... Thanks a lot man!
KingGeorge
  • KingGeorge
no problem at all.

Looking for something else?

Not the answer you are looking for? Search for more explanations.