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

Graphs

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

Definitions

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 .

Degrees

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.

Theorem

Let be a directed graph.

Then:

Proof

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.

Cycles

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

n-cubes

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

Definition

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.

Examples

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

Definition

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 .

Subgraphs

Definition

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

Example

Induced subgraphs

Definition

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 .

Example

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

Matching

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

Theorem

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

Proof

Slides 5-8 on Lecture 19.

Corollary

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

Union of graphs

Definition

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

Examples

Adjacency lists

Definition

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

Example

VertexAdjacent vertices

This adjacency list corresponds to the graph:

Adjacency matrices

Definition

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:

Examples

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

Definition

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:

e.g.

Example

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.

Definition

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.

More

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.

Connectedness

Definition

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

Proposition

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

Proof

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

Definitions

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

Definition

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.

Observations