Graph theory · Definition

Graph

discrete mathematicsgraphs

It is the simplest model of a network: things and the connections between them, regardless of how the picture is drawn.

Definition

A graph \(G\) is a set \(V\) of vertices together with a set \(E\) of edges, each formed by two distinct vertices.

\[G=(V,E),\qquad E\subseteq\{\{u,v\}:\ u,v\in V,\ u\neq v\}\]

A graph can represent road maps, social networks, circuits or dependencies among tasks. Vertices are the objects and an edge \(\{u,v\}\) says that \(u\) and \(v\) are related. Because an edge is an unordered pair, the connection is symmetric: \(\{u,v\}=\{v,u\}\). When direction matters one speaks of directed graphs, studied separately.

The definition above is that of a simple graph: no loops (edges from a vertex to itself) and no repeated edges between the same vertices. With \(n\) vertices there is room for at most \(n(n-1)/2\) edges; the graph having all of them is called complete and written \(K_n\). Other texts allow loops and multiple edges and call these multigraphs.

All that matters is which vertices are joined, not how the graph is drawn. Two different drawings may represent the same graph, and a vertex with no edge, called isolated, is still part of the graph. This contrasts with the Hasse diagram, where height does convey the order.

This concept underlies the rest of the theory: vertex degree, paths, connectedness, trees and cycles, which appear in the following concepts of the topic.

Think about it

How many different simple graphs exist on \(n\) labelled vertices?

Each of the \(n(n-1)/2\) possible pairs is either present or absent, so there are \(2^{n(n-1)/2}\).

Exercises 10

  1. What is the largest number of edges in a simple graph with \(5\) vertices?
  2. A graph has \(V=\{1,2,3,4\}\) and edges \(12,\ 23,\ 34,\ 41,\ 13\). How many pairs of distinct vertices are not joined?
  3. Which of these edge sets cannot belong to a simple graph on \(\{a,b,c\}\)?
  4. Which statement is true in a simple graph?
  5. How many different graphs can be formed on the labelled vertices \(\{1,2,3\}\)?
  6. How many edges are missing from a simple graph with \(6\) vertices and \(9\) edges to have all possible ones?
  7. A simple graph with \(n\) vertices has \(45\) edges, all the possible ones. What is \(n\)?
  8. For which (vertices, edges) pair does a simple graph exist?
  9. How many simple graphs on the labelled vertices \(\{1,2,3,4\}\) have exactly \(5\) edges?
  10. How many simple graphs with labelled vertices \(\{1,2,3,4\}\) are there in total?

References

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §10.1
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §10.1
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §11.1