Graph theory(about the hamilton/bipartite)?

Question

I need help with this problem: Prove that Bn(bipartite) has a Hamilton cycle for n >= 2 by induction

Answer 1

Start with n=2. That's just the configuration:



|X|



Obviously, it has a Hamiltonian cycle. Label the top vertices a1, a2, and the bottom ones b1 and b2. Then just go a1 b1 a2 b2.



Now assume you have Bn, then label them a1 ... an and b1...bn.



Now if you ignore an and bn, you have B(n-1), which has a Hamiltonian path by induction. Then at the end of that path, we can assume you are on the bottom set (the b1...b(n-1) )of the graph, so you finish with an bn. That's the Hamiltonian cycle.

Answer 2

Bn must be the full bipartite graph. There are 2n vertices, call them x_i and y_i where i goes from 1 to n. The graph has an edge between each x_i and every single y_j for a total of n^2 edges. A Hamilton cycle is easy to construct: x_1 to y_1 to x_2 to y_2 to x_3 ... to y_n to x_1 -- hits every vertex, no repeated edges.



If you really have to do this by induction, suppose you have a Hamilton cycle on B_{n-1}. Well, break the cycle at y_{n-1} (it has to go there since it visits every vertex), add in a little path y_{n-1} to x_n to y_n to (wherever the original path went from y_{n-1}). So you're just inserting a little path to the induction hypothesis cycle to cover the two new vertices.



By the way, the base case B_2 follows the pattern above, x_1 to y_1 to x_2 to y_2 to x_1. The problem with B_1 is that it has only one edge, so there's no way to return to the first vertex and complete the cycle.

Answer 3

ok so this is how I see it... A bar graph is right used once you're making some comparisons with particular numerical values. whether, a bar graph will become somewhat cumbersome in case you have too many values or are making too many comparisons. Ex. Max top of a peach tree vs Max top of Apple tree, and so on. A line graph is right used whilst evaluating an outstanding form of information factors. Line graphs are astonishing in displaying differences by the years. Ex. differences in top of a peach tree from 2000 to 2009 A pie graph ( circle graph) is the simplest in that each slice represents a chunk of the entire. So in the journey that your messing with a proportion than Pie Graph is right. Ex. A component of a entire quantity of peaches given to assorted persons. wish this helps somewhat. You get the feel for it the extra you artwork with the countless graphs.