Previous | ToC | Next Labs: Graph Theory. Part 1. Math Alive

## Some Theorems and Exercises

If 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 Kn for n > 2 are not bipartite.

Exercise. All complete graphs Kn for n > 3 are not planar.

Exercise. Which cycle graphs are bipartite?

Exercise. What is the diameter of a cycle graph Cn?

Exercise. List all regular grid graphs.

Exercise. What it the diameter of a grid graph Gm,n?

Exercise. What are the only two regular path graphs? Why?

Exercise. What is the diameter of a path graph Pn?

Exercise. What are the only two regular star graphs?

Exercise. The diameter of a star graph Sn 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 Wn 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?