Graph Theory Notes



Sep 28, 2017



  • Graph: Nodes (vertices) and edges.
  • Isolated: a node without an incident edge.

Type of Graphs

  • Empty graph: no vertex.
  • Multi-graph: 2 or more edges on the same pair of vertices.
  • Simple graph: no loop, no parallel edges.
  • Directed graph (digraph): each edge is represented by an ordered pair (directions of edges matter).
  • Complete graph: simple; every vertex connected to every other distinct vertex.
  • Bipartite graph: vertices can be partitioned into 2 disjoint subsets.
  • Complete Bipartite graph: each node has an edge to every node in the other subset.
  • Sub-graph: node and edge sets are subsets of a graph.


  • Degree of a vertex: number of edges incident on this vertex; loops are counted twice.
  • Total Degree of a graph:



  • Walk: a finite alternating sequence of adjacent vertices and edges.
  • Path: a walk with no repeated edge.
  • Simple: a path with no repeated vertex other than the possibility that.
  • Closed: a walk that starts and ends at the same vertex.
  • Circuit: a closed path.
  • Cycle: a simple circuit.
  • Trivial Circuit: only one vertex, no edge.


  • Connected (for two vertices): there exists some walk in between.
  • Connected (for a graph): every two vertices are connected.
  • Ifis a Connected Component of:
    • is a sub-graph of.
    • is connected.
    • is not a proper sub-graph of any connected sub-graph of.

Adjancency Matrix

  • Out-degree

  • In-degree

Path & Circuit

Hamiltonian Circuit

A closed walk of a graphthat contains:

  • Non-repeated edges forming a subset of.
  • Non-repeated vertices, except the same start/end vertex, forming the full set of.

Euler Path


A path that starts atand ends at, passes every vertex, and traverse every edge ofexactly once.

Euler Circuit

A closed walk of a graphcontaining:

  • Non-repeated edges forming the full set
  • Possibly repeated vertices forming the full set


  • Tree: a connected graph only containing trivial circuits.
  • Acyclic Direct Graph: a directed graph without a non-trivial directed cycle.
  • Leaf (Terminal Vertex) of a tree with 2 or more vertices: a vertex of degree 1.

Graph Isomorphism

A graphis isomorphic to another graphif and only if there exists two bijections mapping the vertex sets and edges sets respectively:


  1. The total degree of a graph equals twice the number of edges.
  2. In any graph, the number of vertices of odd degree is even.
  3. If,are vertices on a circuit in, then if one edge is removed from this circuit, there still exists a path in between.
  4. Ifis connected and contains a circuit, then an edge of the circuit can be removed without disconnecting.
  5. An Euler path fromtoexists ⇔is connected,andhave odd degree, and all other vertices ofhave even degree.
  6. A graphcontains an Euler circuit ⇔is connected, and every vertex ofhas even degree.
  7. Ifis a connected graph withvertices,, such thatfor any pair of nonadjacent verticesandin, thenhas a Hamilton circuit.
  8. Any tree that hasvertex has at least one vertex of degree.
  9. Any tree ofvertices hasedges.
  10. If a connected graph hasvertices andedges, it is a tree.
  11. If a graphcontains a Hamiltonian circuit, thenmust contain a sub-graphthat:
    • Is connected.

Copyright ©Jennifer