80.2K

Verified Solution

Link Copied!

A regular graph is a graph where all vertices have the same number of edges. a) Draw a simple 4-regular graph that has 9 vertices. (i.e. a vertex with 9 vertices where every vertex has 4 edges connected, and no two vertices have more than one edge between them) (Hint: arrange 6 of the vertices/edges as a hexagon, put one vertex inside, one vertex above, and one vertex below. Find connections that make 4 edges from each vertex.) b) Write out the adjacency matrix for this graph c) What in an adjacency matrix tells you how many edges emanate from a certain vertex? d) Use the adjacency matrix to show that there does not exist a 3-regular graph with 5 vertices (In general, an odd regular graph must have an even number of vertices) Hint: Start with this matrix below and try to fill it in to make it 3-regular. Begin with the second row (and this implies second column by symmetry) and continue row by row. Hint: There are 3 cases for filling in the second row while keeping it 3-regular: (1, 0, 1, 1, 0),(1, 0, 1, 0, 1),(1, 0, 0, 1, 1) The third row would have 1 or 2 cases depending on which case for row 2 you pick Disprove all of these cases 0 1 1 1 0 1 0 1 0 1 0 0 0

7. A "regular" graph is a graph where all vertices have the same number of edges. a) Draw a simple " 4-regular" graph that has 9 vertices. (i.e. a vertex with 9 vertices where every vertex has 4 edges connected, and no two vertices have more than one edge between them) (Hint: arrange 6 of the vertices/edges as a hexagon, put one vertex inside, one vertex above, and one vertex below. Find connections that make 4 edges from each vertex.) b) Write out the adjacency matrix for this graph c) What in an adjacency matrix tells you how many edges emanate from a certain vertex? d) Use the adjacency matrix to show that there does not exist a 3-regular graph with 5 vertices (In general, an odd regular graph must have an even number of vertices) Hint: Start with this matrix below and try to fill it in to make it 3-regular. Begin with the second row (and this implies second column by symmetry) and continue row by row. Hint: There are 3 cases for filling in the second row while keeping it 3-regular: (1,0,1,1,0),(1,0,1,0,1),(1,0,0,1,1) The third row would have 1 or 2 cases depending on which case for row 2 you pick Disprove all of these cases 0 1 1 1 0 10 0 1 0 1 0

Answer & Explanation Solved by verified expert

See Answer