Question

Question 5. Prove by contradiction that every circuit of length at least 3 contains a cycle Question 6. Prove or disprove: There exists a connected graph of order 6 in which the distance between any two vertices is even Question 7. Prove formally: If a graph G has the property that every edge in G joins a vertex of odd degree to a vertex of even degree, then G is bipartite and has even size. Question 8. Prove formally: Suppose G is a connected graph that has a circuit that visits every edge exactly once. Then every vertex of G has even degree Question 9. The n-dimensional hypercube is the graph whose vertex set consists of all binary strings of length n, and whose edge set consists of all pairs of vertices whose binary strings differ in exactly one position (a) Draw the 2-dimensional hypercube and the 3-dimensional hypercube, labeling the vertices with their binary strings (b) Prove that the n-dimensional hypercube is bipartite for all n

Please write your answer clearly and easy to read.

Please only answer the ones you can. I will upvote all the submitted answers.

Answer 1