Week 13 - Graphs A

7.1 - Introduction to graph theory: basic concepts

  • Computer scientists create abstractions of real world problems for representing and manipulating with a computer.
  • One example, is logic which is used to define a computer circuits.
  • Scheduling final exams is another example:
    • Has to take into account associations between courses, students and rooms.
    • These associations (connections) between items are modelled by graphs.
  • Graphs are discrete structures consisting of vertices (nodes) and edges connecting them.
  • Graph theory is an area in discrete math which studies these type of discrete structure.
  • What is a graph?
    • Graphs are discrete structures consisting of vertices (nodes) and edges connecting them.
    • Graph theory is an area that studies these structures.
  • Origins of graph theory:
    • First problem in graph theory is Seven Bridges of Konigsbert problem solved by Loenhard Euler in 1735.
      • 2 islands are connected by 7 bridges.
      • Can you walk across all 7 bridges only once.
    • In a paper published in 1726, he showed that it is impossible.
  • Applications of graphs
    • Used in a variety of disciplines.
    • Examples:
      • Networks.
      • Road maps.
      • Solving shortest path problems between cities.
      • Assigning jobs to employees in an organisation.
      • Distinguishing chemical compound structures.

Lesson 7.103 - Definition of a graph

  • Graph
    • Discrete structures consisting of vertices and edges connecting them.
  • Formal definition:
    • GG is an ordered pair G=(V,E)G=(V, E).
    • VV is a set of nodes, or vertices.
    • EE is a set of edges, lines or connections.
  • Vertex

    • Basic element of a graph.
    • Drawn as a node or a dot.
    • Set of vertices of G is usually denoted by V(G) or V.


  • Edge

    • A is a link between 2 vertices.
    • Drawn as a line connecting two vertices.
    • A set of edges in a graph GG is usually denoted by E(G)E(G) or EE.


  • Adjacency

    • Two vertices are said to be adjacent if they are endpoints of the same edge.
    • Two edges are said adjacent if they share the same vertex.
    • If a vertex v is an endpoint of an edge e, then we say that e and v are incident.


  • v1v_1, v2v_2 are endpoints of the edge e1e_1. We say that v1v_1 and v2v_2 are adjacent.

  • The edges e1e_1 and e7e_7 share the same vertex v1v_1. We say that e1e_1 and e7e_7 are adjacent.
  • The vertex v2v_2 is an endpoint of the edge e1e_1. We say that e1e_1 and v2v_2 are incident.
  • Loops and parallel edges

    • Consider this graph:


    • v2v_2 and v5v_5 are linked with 2 edged: (e_6 and e_8). e_6 and e_8 are considered Parallel Edges.

    • v1v_1 is linked by e9e_9. We call the edge e9e_9 a Loop.
    • Directed Graphs
    • Aka digraph.
    • Graph where edges have a direction.


  • e1e_1 is a connection from v1v_1 to v2v_2 but not from v2v_2 to v1v_1

  • e6e_6 is a connection from v2v_2 to v5v_5 whereas e8e_8 is a connection from v5v_5 to v2v_2.

Lesson 7.105 Walks and paths in a graph

  • Definition of a Graph Walk

    • Sequences of vertices and edges of a graph.
      • Vertices and edges can be repeated.
    • A walk of length k in a graph is a succession of kk (not necessarily different) edges of form:
      • uvuv, vwvw, wxwx, ..., yzyz
    • Example


    • Example 2


  • Graph Trail

    • A trail is a walk where no edge is repeated.
    • In a trail, vertices can be repeated but no edge is repeated.


  • Graph Circuit

    • A circuit is a closed trail.
    • Circuits can have repeated vertices only.


  • Graph Path

    • A path is a trail in which neither vertices nor edges are repeated.
    • Length of path is given in number of edges it contains.
  • Graph Cycle

    • Closed path consisting of edges and vertices where a vertex is reachable from itself. week-13-graph-cycle
  • Seven Bridges of Koenigsberg

    • Is there a walk that passes each of the 7 bridges once.
    • He made a network linked with lines that shows:
      • No walk that uses each edge exactly once (even if we allow the walk to start and finish in diff places)
  • Euler's Path

    • A Eulerian path in a graph is a path that uses each edge precisely once.

      • If the path exists, the graph is called traversable.


  • Hamiltonian path

    • Hamiltonian path (aka traceable path) is a path that visits each vertex exactly once.
    • A graph that contains a Hamiltonian path is called a traceable graph.


  • Hamiltonian cycle

    • A Hamilton cycle is a cycle that visits each vertex exactly once (except for the starting vertex, which is visited once at the start and once again at end).


    • Connectivity

      • An undirect graph is connected if
        • You can get from any node to any other by following a sequence of edges OR
        • any two nodes are connected by a path.
      • Example of connected graph:


    • Unconnected graph


    • Strong connectivitiy

      • A directed graph is strongly connected if there is a directed path from any node to any other node.


    • Example of a graph that's not strongly connected


    • No direct path from v_4 to any of the other 3 vertices.
    • Transitive Closure
    • Given a digraph G, the transitive closure of G is the digraph G such that: G has the same verticies as G
    • If G has a directed path from uu to vv ($u \ge v$), G* has a directed edge from uu to vv.


    • Transitive closure provides reachability information about a digraph.

Lesson 7.107 - The degree sequence of a graph

  • Degree of Vertices

    • The number of edges incident on v.
    • A loop contributes twice to the degree.
    • An isolated vertex has a degree of 0.


  • For directed graphs:

    • In-deg (v): number of edges for which v is the terminal vertex.
    • Out-deg (v): number of edges for which v is the initial vertex.
    • deg(v) = Out-deg(v) + In-deg(v)
    • A loop contributes twice to the degree, as it contributes 1 to both in-degree and out-degree.
  • Degree Sequence of a Graph

    • Given an undirected graph G, a degree sequence is a monotonic nonincreasing sequence of the vertex degress of all the vertices G.


    • Properties of graph degree sequence:

      • Degree sequence property 1
        • The sum of degree sequence of a graph is always even.
          • It is impossible to construct a graph where the sum of degree sequence is odd.
      • Degree sequence property 2

        • Given a graph G, the sum of the degree sequence of G is twice the number of edges in G.
        • Number of edges(G) = (sum of degree sequences of G) / 2


    • Exercise: which of the 2 degree sequences below is it possible to construct a graph with?

      • 3, 2, 2, 1
        • Sum of sequence = 3 + 2 + 2 =1 = 8
        • Can build a graph with this.
        • Number of edges = 8/2 = 4
      • 3, 3, 2, 1
        • Sum of sequence = 3 + 3 + 2 + 1 = 9
        • Can't build a graph with this.

7.109 - Special graphs: simple, r-regular and complete graphs

  • Simple Graph

    • A graph without loops and parallel edges.


    • Given a simple graph G with n vertices, then the degree of each vertex of G is at most equal to n-1.
    • Proof
      • Let vv be a vertex of G such that deg(v) > n-1
      • However, we have only n-1 other vertices for v to be connected to.
      • Hence, the other connections can only be a result of parallel edges or loops
    • Exercise
    • Can we draw a simple graph with the following degree sequences?
      • 4, 2, 2, 2
        • Sum(deg sequence) is even so we can construct a graph
        • However, no other vertex has degree of 4. There are only 3 other vertices to be connected to, so it has to contain a loop or parallel edges.
      • 4, 3, 3, 2, 2
        • Yes, it can be done. week-13-simple-graph-solution
  • Regular Graph and R-Regular Graph

    • A graph is regular if all local degrees are the same number.
    • A graph G where all vertices the same degree, rr, is called a r-regular graph.


    • Given a r-regular G with n vertices, then the following is true:

      • Degree sequence of G=r,r,r,...,r(n times)G = r, r, r, ..., r (\text{n times})
      • Sum of degree sequence of G=r x nG = r \ x \ n
      • Number of edges in G=r x n2G = \frac{r \ x \ n}{2}


  • Special regular graphs: cycles


  • Exercise
    • Can we construct a 3-regular graph with 4 vertices?
    • Can we construct a 4-regular graph with 5 vertices?
      • 3x5 = 15
      • Sum is odd, so cannot great a regular graph.
  • Complete Graph

    • A Simple Graph where every pair of vertices are adjacent (linked with an edge).
    • A vertex on its own is a complete graph.


    • A complete graph with n vertices, k_n, has these properties:
      • Every vertex has a degree (n1)(n-1)
      • Sum of degree sequence n(n1)n(n-1)
      • Number of edges n(n1)/2n(n-1)/2