Some Theorems and ExercisesIf you undestood the definitions on the previous page, you can try to prove the following theorems and do the following exercises. Theorem. All the graphs you studied on the previous page: complete, cycle, grid, path, star, wheel are connected. Theorem. All cycle graphs, grid grahs, path graphs, star graphs and wheel graphs are planar. Theorem. All complete graphs and cycle graphs are regular. Theorem. All grid graphs, path graphs, and star graphs are bipartite. Theorem. The diameter of a complete graph is always 1. Exercise. All complete graphs K_{n} for n > 2 are not bipartite. Exercise. All complete graphs K_{n} for n > 3 are not planar. Exercise. Which cycle graphs are bipartite? Exercise. What is the diameter of a cycle graph C_{n}? Exercise. List all regular grid graphs. Exercise. What it the diameter of a grid graph G_{m,n}? Exercise. What are the only two regular path graphs? Why? Exercise. What is the diameter of a path graph P_{n}? Exercise. What are the only two regular star graphs? Exercise. The diameter of a star graph S_{n} for n > 1 is always 2. Exercise. Wheel graphs are never bipartite. Exercise. What is the only regular wheel graph? Exercise. The diameter of a wheel graph W_{n} for n > 4 is always 2. Exercise. What cycle graph is a complete graph? Exercise. What grid graph is a cycle graph? Exercise. What grid graphs are path graphs? Exercise. What star graph is a path graph? Exercise. What wheel graph is a complete graph?
