Graph Theory Lessons


previous index next Lesson 18: Star Graphs

Suppose we start with n vertices, choose one special vertex and then draw edges from the special vertex to every other vertex. The graph we would obtain is called the star on n vertices, Sn. Figure 18.1 shows the star on ten vertices, S10.

Star on 10 vertices
Fig 18.1, The star S10

Java Web Start Activity:
To get examples of star graphs, launch the Java Web Start application by clicking on the link below this paragraph. Once the application is running, click on the + button to increase the number of vertices. The - button decreases the number of vertices.

Petersen activity:
To get a star graph in the Petersen program use the menu options Graph | Named Graph | Trees | Star. Take a look at a few of the graphs Sn for other values of n and then answer the questions below.

the star graph on 30 vertices
Fig 18.2, The graph S30

Use the Petersen program to examine some star graphs and answer the following questions:
  1. What is the chromatic number of S3, S5, S8
  2. Are stars bipartite ?
  3. Which complete bipartite graph is isomorphic to Sn?


© C. Mawata