GraphsUndirected graphsDirected graphsDefinitionsDirected graphDegreesTheoremProofComplete graphsCyclesn-cubesBipartite graphsDefinitionExamplesShow that is bipartiteShow that is not bipartiteComplete Bipartite GraphsDefinitionSubgraphsDefinitionExampleInduced subgraphsDefinitionExampleBipartite graphsMatching in Bipartite GraphsMatchingMaximum matchingPerfect/complete matchingsHall's Marriage TheoremTheoremProofCorollaryUnion of graphsDefinitionExamplesAdjacency listsDefinitionExampleAdjacency matricesDefinitionExamplesExample 1Example 2Adjacency matrices (continued)Isomorphism of graphsDefinitionExamplePaths (in undirected graphs)DefinitionMoreConnectednessDefinitionPropositionProofConnected componentsStrongly connected graphsEuler/Hamiltonian paths and circuitsDefinitionsGraph colouringDefinitionObservations


Undirected graphs

For a set , let denote the set of -element subsets of . (Equivalently, is the set ofo all -combinations of .)

A (simple, undirected) graph , consists of a set of vertices , and a set of edges.

Every edge has two distinct vertices as endpoints, and such vertices and are then said to be adjacent in the graph .

The above definitions allow for infinite graphs, where .

Directed graphs


Directed graph

A directed graph, , consists of a set of vertices , and a set of directed edges.

Each directed edge has a start (tail) vertex , and an end (head) vertex .


The in-degree of a vertex , denoted , is the number of edges directed into . The out-degree of , denoted , is the number of edges directed out of . Note that a loop at a vertex contributes 1 to both in-degree and out-degree.


Let be a directed graph.



The first sum counts the number of outgoing edges over all vertices and the second sum counts the number of incoming edges over all vertices. Both sums must be .

Complete graphs

A complete graph on n vertices, denoted by , is the simple graph that contains exactly one edge between each pair of distinct vertices.

A complete graph has vertices and edges.


A cycle for consists of vertices and edges {},{,},,{,}, {,}.


An n-dimensional hypercube or n-cube, is a graph with vertices representing all bit strings of length , where there is an edge between two vertices iff they differ in exactly one bit position.

For example:

Bipartite graphs


An equivalent definition of a bipartite graph is one where it is possible to color the vertices either red or blue so that no two adjacent vertices are the same color.


Show that is bipartite

Partition the vertex set into and .

Show that is not bipartite

If we partition vertices of into two non-empty sets, one set must contain two vertices. But every vertex is connected to every other. So, the two vertices in the same partition are connected. Hence, is not bipartite.

Complete Bipartite Graphs


A complete bipartite graph is a graph that has its vertex set partitioned into two subsets of size and of size such that there is an edge from every vertex in to every vertex in .



A subgraph of a graph is a graph , where and . A subgraph of is a proper subgraph of if .


Induced subgraphs


Let be a graph. The subgraph induced by a subset of the vertex set is the graph , whose edge set contains an edge in iff both endpoints are in .


Here is and its induced subgraph induced by .

Bipartite graphs

A bipartite graph is a (undirected) graph whose vertices can be partitioned into two disjoint sets , with and , such that for every edge , such that and . In other words, every edge connects a vertex in with a vertex in .

This is an alternative definition to the coloring definition.

Matching in Bipartite Graphs


A matching , in a graph , is a subset of edges, , such that there does not exist two distinct edges in that are incident on the same vertex. In other words, if , then either or .

i.e. the set of pairwise non-adjacent edges; that is, no two edges share a common vertex.

Maximum matching

A maximum matching in graph is a matching in with the maximum possible number of edges.

Perfect/complete matchings

For a graph , we say that a subset of edges, , covers a subset of vertices, , if for all vertices there exists an edge , such that is incident on , i.e., such that , for some vertex .

In a bipartite graph with bipartition , a complete matching with respect to , is a matching that covers , and a perfect matching is a matching, , that covers .

Figure (b) above is an example of a perfect matching.

Hall's Marriage Theorem


For a bipartite graph , with bipartition , there exists a matching that covers iff .


Slides 5-8 on Lecture 19.


A bipartite graph with bipartition () has a perfect matching iff and .

Union of graphs


The union of two simple graphs and is the simple graph with vertex set and edge set . The union of and is denoted by .


Adjacency lists


An adjacency list represents a graph (with no multiple edges) by specifying the vertices that are adjacent to each vertex.


VertexAdjacent vertices

This adjacency list corresponds to the graph:

Adjacency matrices


Suppose that is a simple graph where . Arbitrarily list the vertices of as .

The adjacency matrix, , of , with respect to this listing of vertices, is the matrix with its entry = when and are adjacent, and when they are not adjacent.

In other words: and:


Example 1

Corresponds to the graph:

Example 2

Corresponds to the graph:

Adjacency matrices (continued)

Also, since there are no loops, each diagonal entry is zero: .

Isomorphism of graphs


Two (undirected) graphs and are isomorphic if there is a bijection, , with the property that for all vertices :

Such a function is called an isomorphism.

Intuitively, isomorphic graphs are the same except for the renamed vertices.

It is difficult to determine whether two graphs are isomorphic by brute force: there are bijections between vertices of -vertex graphs.

To show that two graphs are not isomorphic, we can find a property that only one of the two graphs has. Such a property is called graph invariant:



These graphs are not isomorphic. This is because in , a must correspond to or , since these are the vertices of degree in .

But each of these vertices is adjacent to another vertex of degree in , which is not true for in . So, and can not be isomorphic.

Paths (in undirected graphs)

Informally, a path is a sequence of edges connecting vertices.


For an undirected graph , an integer , and vertices , a path (or walk) of length from to in is a sequence:

of interleaved vertices and edges , such that and , and such that .

Such a path starts at and ends at . A path of length is called a circuit (or cycle) if and the path starts and ends at the same vertex, i.e. .

A path or circuit is called simple if it does not contain the same edge more than once.


Don't confuse a simple undirected graph with a simple path.

There can be a simple path in a non-simple graph, and a non-simple path in a simple graph.

A path is tidy when no vertex is repeated.

A path is simple when no edge is repeated.



An undirected graph is called connected if there is a path between every pair of distinct vertices. It is called disconnected otherwise.


There is always a simple, and tidy, path between any pair of vertices , of a connected undirected graph .


Read slide 7

Connected components

A connected component of a graph is a maximal connected subgraph of , meaning is connected and and but is not a proper subgraph of a larger connected subgraph of .

Strongly connected graphs

A directed graph is strongly connected if for every pair of vertices in and in , there is a directed path from to , and a directed path from to .

It is weakly connected if there is a path between every pair of vertices in in the underlying undirected graph (meaning we ignore the direction of edges).

A strongly connected component of a directed graph , is a maximal strongly connected subgraph of which is not contained in a larger strongly connected subgraph of .

Euler/Hamiltonian paths and circuits


An Euler path in a multigraph is a simple path that contains every edge of . (so every edge occurs exactly once in the path)

An Euler circuit in a multigraph is a simple circuit that contains every edge of . (so every edge occurs exactly once in the circuit)

A Hamiltonian path is a multigraph is a simple path that passes through every vertex (not necessarily each edge), exactly once.

A Hamiltonian circuit is a multigraph is a simple circuit that passes through every vertex (not necessarily each edge), exactly once.

Graph colouring


Suppose we have disinct colours with which to colour the vertices of a graph. Let . For an undirected graph, , an admissable vertex -colouring of is a function , such that , .

For an integer , we say an undirected graph , is -colourable if there exists a -colouring of .

The chromatic number of , denoted , is the smallest positive integer , such that is -colourable.