Supplement to Lesson 2: A Glossary of Graphs

by Dale Winter


Some graphs have special properties. For example, the graphs,



are both graphs on five vertices. In the graph on the left, no vertices are connected at all, whereas in the graph on the right, every vertex is joined to every other vertex by exactly one edge. This graph on the left is called the null graph on five vertices, and the graph on the right is called the complete graph on five vertices.

Definition A graph whose edge set is empty is called a null graph. A null graph on n vertices is denoted by Nn.

Definition A simple graph in which every pair of distinct vertices are adjacent is called a complete graph. The complete graph on n vertices is denoted by Kn.



  • A complete graph must be a simple graph (by the definition of a complete graph). Does a null graph have to be a simple graph? Why or why not?

  • How many edges does the complete graph on n > 0 vertices have? You might like to draw the complete graphs on 1, 2, 3, 4, etc. vertices, and see whether or not you can spot a pattern. Can you give a mathematical argument to show that your formula for the number of edges is correct?

  • Is it possible for a simple graph on n > 0 vertices to have more edges than Kn ? Try to give an argument or and example to back up your conclusions.



    • Definition A connected, 2-regular graph is called a circuit graph. The circuit graph on n > 3 vertices is denoted by Cn.



  • Is it possible to have circuit graphs with 1 or 2 vertices? If so, what would they look like. If not, what goes wrong with the definition?



    • Definition The star graph, Sn, has n vertices v1 , . . . , vn with single edges joining v1 to vj for . For example,



    Definition The wheel graph, Wn, has n vertices v1 , . . . , vn with single edges joining v1 to vj for . It also has single edges joining vj to vj + 1 for , and a single edge joining vn to v2. For example,




    Definition Suppose that the vertex set of a graph G can be split in two non-empty, disjoint sets, A and B in such a way that every edge of G joins a vertex of A to a vertex of B. The graph G is then said to be a bipartite graph.



  • The stipulation that the sets A and B are non-empty sets might seem a bit pedantic. However, if it is omitted, there are quite serious consequences. See if you can prove: If the requirement that sets A and B are non-empty is dropped, then every graph is a bipartite graph. If this was the case, there would be little sense in calling a graph a bipartite graph - we could just call it a graph, and save some typing.

  • The following graphs are all bipartite graphs. Can you show how they satisfy the definition given above?


    • Are any of the special types of graph defined so far examples of bipartite graphs?


    Definition Suppose that G is a bipartite graph, and that the vertex set can be split into non-empty disjoint sets A and B. If every vertex of A is joined to every vertex of B, then G is called a complete bipartite graph. Such a graph is denoted by Km, n where A contains m vertices, and B contains n vertices, and every vertex in A is joined to every vertex in B by a single edge. For example,




    New Graphs from Old

    There are several constructions or operations that help to generate further examples of graphs from the examples we already have. The three discussed here are the sum, the union, and the complements of graphs.

    Definition If two graphs are taken to be G1 = (V(G1), E(G1)) and G2 = (V(G2), E(G2)), where V(G1) and V(G2) are assumed to be disjoint, then their union G1 U G2 is defined to be the graph with vertex set V(G1) U V(G2), and edge set E(G1) U E(G2). For example,



    Definition If G and H are graphs with disjoint vertex sets, then their sum, G + H, is the graph with vertex set V(G) U V(H) and edge set consisting of the union of E(G) and E(H) together with single edges joining every vertex of G to every vertex of H. For example,






  • Can you find a relationship between wheel graphs, null graphs and circuit graphs?

  • Can you find a relationship between star graphs and null graphs?



    • Definition If G is a simple graph with vertex set V(G) then the complement, , of G is the graph with the same vertex set as G, and edge set given by the rule:

    Two vertices v and w are adjacent in if and only if they are not adjacent in G.

    For example,





  • What is the complement of the complete graph on n vertices?

  • Can you find an argument that justifies the proposition:

    • Proposition The complement of Km, n is Km U Kn.

    As you work on an argument, you might like to try some examples to see how the mathematics works.

  • Can you find an argument that justifies the following proposition:

  • Proposition Suppose that G is a k-regular graph on n vertices. Then the complement of G is a (n - k - 1)-regular graph on n vertices.

    • As you work on an argument, you might like to try some examples to see how the mathematics works.

    Back to MMS Main Page || Back to Graph Theory Contents Page