What is a Graph?

by Dale Winter

In this course, we will study mathematical objects called graphs. Often, when the word graph is used in a mathematical setting, people think of something resembling:




In this situation, the word graph is short for graph of a function. This kind of graph can be precisely defined to be a set of ordered pairs. For example, the graph of a function f may be defined to be the set:



The kind of graphs that we will study are sometimes called combinatorial graphs to distinguish them from the graphs described above. Combinatorial graphs can sometimes be represented pictorially as networks of dots (called vertices) connected by lines (called edges). Examples include:

  • The Tetrahedral Graph:




    •

  • The Octahedral Graph:




  • The Cube Graph:






    • The pictorial representations of the cube and octahedral graphs show how they got their names - both can be drawn so that they resemble a drawing of a cube or an octahedron.

  • Can you explain why the graph:




    • is called the tetrahedral graph?

  • What do you think would be appropriate names for the following graphs?






  • Why do you think that the points on the graph are called vertices and the lines that join the points are called edges? If you had to define the term face in the context of graph theory, how would you define it?




    • Graphs from an Abstract Viewpoint

    Pictures of graphs showing all of the edges and vertices are great ways to represent a graph. It is immediately clear which vertices are joined by edges, and you can often recognize the graph from its picture. For example, if you were given a very abstract description of the cube graph like:

    The graph has eight vertices and 12 edges. Every vertex meets exactly three vertices.

    it might take you some time and effort to recognize that this is the cube graph. If you see a picture that looks exactly like a cube, then you know immediately that you are dealing with the cube graph.

    However, pictorial representations of graphs have their limitations, too. For example, if you wanted to prove a theorem about graphs, and all you had were pictorial representations, then your proof might have to consist of drawing every single, possible graph, and then demonstrating the truth of your theorem for each picture that you have drawn. A pretty time-consuming process, to say the least.

    To help us find other ways of describing graphs, consider the following definitions:

    Definition A graph G consists of a set of vertices and a set of edges, where each edge joins an unordered pair of vertices. The set of vertices of G is denoted by V(G) and the set of edges is denoted by E(G).

    Definition A loop is an edge that joins a vertex to itself. A multiple edge occurs when there is more than one edge joining a pair of vertices.

    Definition A simple graph is a pair (V(G), E(G)) where V(G) is a non-empty finite set of elements, and E(G) is a finite set of unordered pairs of distinct elements of V(G).


  • Do these definitions capture all of the important aspects of a graph? Are there any features of the (pictorial) examples of graphs shown earlier that are not captured by these definitions?

  • Using these definitions, can you come up with different ways of describing a graph, other than drawing a picture of it?

  • It seems that the definitions of graph and simple graph given above are very similar. Are they, in fact, the same thing? If you think so, give an argument. If you think not, give some example which show how graphs and simple graphs differ.

  • What applications can you think of for graphs? What kinds of things might graphs be good at describing? One application that occurs to me is the network of neurons in our brains. The vertices would be the neurons, and the edges would be the nerves connecting the neurons. What other examples can you think of? Can you think of any examples where a graph is almost a great description, but doesn't quite describe everything in the application?


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