Graph Basics

In a graph, the objects are represented with dots and their connections are represented with lines like those in . displays a simple graph labeled G and a multigraph labeled H. The dots are called vertices; an individual dot is a vertex, which is one object of a set of objects, some of which may be connected. We often label vertices with letters. For example, Graph G has vertices a, b, c, and d, and Multigraph H has vertices, e, f, g, and h. Each line segment or connection joining two vertices is referred to as an edge. H is considered a multigraph because it has a double edge between f and h, and a double edge between h and g. Another reason H is called a multigraph is that it has a loop connecting vertex e to itself; a loop is an edge that joins a vertex to itself. Loops and double edges are not allowed in a simple graph.

To sum up, a simple graph is a collection of vertices and any edges that may connect them, such that every edge connects two vertices with no loops and no two vertices are joined by more than one edge. A multigraph is a graph in which there may be loops or pairs of vertices that are joined by more than one edge. In this chapter, most of our work will be with simple graphs, which we will call graphs for convenience.

It is not necessary for the edges in a graph to be straight. In fact, you can draw an edge any way you want. In graph theory, the focus is on which vertices are connected, not how the connections are drawn (see ). In a graph, each edge can be named by the two letters of the associated vertices. The four edges in Graph X in are ab, ac, ad, and ae. The order of the letters is not important when you name the edge of a graph. For example, ab refers to the same edge as ba.

Condensed — the full section is in OpenStax Contemporary Mathematics.

When graphs are used to model and analyze real-world applications, the number of edges that meet at a particular vertex is important. For example, a graph may represent the direct flight connections for a particular airport as in . Representing the connections with a graph rather than a map shifts the focus away from the relative positions and toward which airports are connected. In , the vertices are the airports, and the edges are the direct flight paths. The number of flight connections between a particular airport and other South Florida airports is the number of edges meeting at a particular vertex. For example, Key West has direct flights to three of the five airports on the graph. In graph theory terms, we would say that vertex FYW has degree 3. The degree of a vertex is the number of edges that connect to that vertex.

Graphs are also used to analyze regional boundaries. The states of Utah, Colorado, Arizona, and New Mexico all meet at a single point known as the “Four Corners,” which is shown in the map in .

In , each vertex represents one of these states, and each edge represents a shared border. States like Utah and New Mexico that meet at only a single point are not considered to have a shared border. By representing this map as a graph, where the connections are shared borders, we shift our perspective from physical attributes such as shape, size and distance, toward the existence of the relationship of having a shared boundary.

Geographical maps are just one of many real-world scenarios which graphs can depict. Any scenario in which objects are connected to each other can be represented with a graph, and the connections don’t have to be physical. Just think about all the connections you have to people around the world through social media! Who is in your network of Twitter followers? Whose Snapchat network are you connected to?

• Graphs and multigraphs represent objects as vertices and the relationships between the objects as edges.
• The degree of a vertex is the number of edges that meet it and the degree can be zero.
• An edge must have a vertex at each end.
• Multigraphs may contain loops and double edges, but simple graphs may not.