The graph on v in which two such sequences form an edge if

Question

A. Let d ∈ N and V := {0, 1} d ; thus, V is the set of all 0-1 sequences of length d. The graph on V in which two such sequences form an edge if and only if they differ in exactly one position is called the d-dimensional cube. Determine the average degree, number of edges, diameter, girth and circumference of this graph. (Hint for the circumference: induction on d).

B. Let G be a graph containing a cycle C, and assume that G contains a path of length at least k between two vertices of C. Show that G contains a cycle of length at least √ k. Hint [1]: Consider how the path intersects C. Where can you see cycles, and can they all be short?

Answer 1

This assignment is about to theory of computation and using different-2 formulas. Make sure use it via process. You will not remove any step between the questions. A. Let d ? N and V: = {0, 1} d ; consequently, V is the set of all 0-1 sequences of length d. The graph on V in which two these sequences form a perimeter if and only if they be different in precisely one position is said the d-dimensional cube. Find out the average degree, number of edges, diameter, girth and perimeter of this graph. As giving note: please be sure to read below instructions carefully, you are provided all answers folders as above instructions. You can place an apply for solution file via left side button.