Graph Theory (Edexcel International AS Maths: Decision 1)

What is graph theory?

• Graph theory is the study of graphs, which are mathematical structures used to represent objects and the connections between them
  • Graphs can be used in modelling many real-life applications, e.g. electrical circuits, flight paths, maps etc.

What are the different parts of a graph?

• A graph is made up of a number of points (vertices or nodes) that are connected by lines (edges or arcs)  
• A vertex (node) can represent an object, a place or a person
  • Adjacent vertices are connected by an edge 
  • Vertices are usually labelled with a letter, e.g. A, B, C...
    • The list of vertices in a graph is sometimes called the vertex set
• An edge (arc) forms a connection between two vertices
  • Edges are described by the nodes they connect, e.g. AB, AC, BE...
    • The list of edges in a graph is sometimes called the edge set
  • Adjacent edges share a common vertex
  • There may be multiple edges connecting two vertices
  • An edge that starts and ends at the same vertex is called a loop
• Typically a graph will be drawn such that edges do not overlap
  • Note that if a graph is drawn with overlapping edges, the edges are not connected at points where they overlap
  • Edges are only connected at vertices

What are the properties of graphs?

• The edges of a graph may be assigned a numerical value
  • This value is called the weight (of an edge)
  • Weight is often a measure such as distance, time or money

• A walk is a finite series of edges in a graph that starts at one vertex and moves from vertex to vertex
  • The (total) weight of a walk is the sum of the weights of the edges that it consists of
• A path is a walk where no vertex is visited more than once
• A trail is a walk where no edge is visited more than once
  • Every path is also a trail but not every trail is a path
• A cycle (or circuit) is a path that starts and finishes at the same vertex
  • It is also known as a closed path
• A tour is a walk that visits every vertex and returns to its start vertex

What are the types of graph?

• A connected graph is a graph in which all of its vertices are connected to each other
  • Two vertices are connected if there is a path between them
    • There does not need to be an edge connecting the pair of vertices

• A complete graph is a graph in which each vertex is connected by an edge to each of the other vertices
  • A complete graph with n vertices is labelled K_n

• If the edges of a graph have a weight, the graph is known as a weighted graph (or network)
  • Networks are not usually drawn to scale

• If the edges of a graph are assigned a direction, they are known as directed edges and the graph is known as a digraph
  • Directed edges of a graph can only be traversed in the direction indicated

• A simple graph is undirected and unweighted and contains no loops or vertices connected by multiple edges
• Given a graph G, a subgraph is a graph which contains only edges and vertices that appear in G
• A tree is a connected graph that does not contain any cycles
• A spanning tree is a subgraph (of a graph G) which is also a tree, and which contains all the vertices from G

• Isomorphic graphs are graphs which show the same information but which are drawn in different ways
  • The number of vertices and the number of edges connected to each vertex are the same