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

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 .

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.

Then:

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 .

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:

- A vertex on a
**3-cube**would have edges connecting to vertices , and . - A vertex on a
**6-cube**would have edges connecting to vertices , , , , and .

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.

Partition the vertex set into and .

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.

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 .

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 .

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.

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.

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

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.

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 .

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

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

Vertex | Adjacent vertices |
---|---|

This adjacency list corresponds to the graph:

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:

Corresponds to the graph:

Corresponds to the graph:

- The adjacency matrix of an undirected graph is
**symmetric**:

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

Adjacency matrices can also be used to represent graphs with loops and multi-edges.

When multiple edges connect vertices and , (or if multiple loops present at the same vertex), the entry equals the number of edges connecting the pair of vertices.

### Example

Corresponds to the graph:

Adjacency matrices can represent directed graphs in exactly the same way.

The matrix for a directed graph has a in its position if there is an edge from to , where is a list of the vertices.

In other words:

**Note**: The adjacency matrix for a directed graph does not have to be symmetric.A

**sparse**graph has few edges relative to the number of possible edges.Sparse graphs are more efficient to represent using an adjacency list than an adjacency matrix. But for a

**dense**graph, an adjacency matrix is often preferable.

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.

- Number of vertices of given degree
- Degree sequence (list of the degrees)
- Number of edges
- Number of cycles

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.

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 .

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 .

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 .

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.

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.

Any graph with vertices is -colourable.

The

**-clique**, i.e., the complete graph on vertices, has chromatic number . All its vertices must get assigned different colours in any admissable colouring.The

**clique number**, , of graph is the maximum positive integer , such that is a subgraph of .For all graphs , .

In general, .

e.g. has and . Note that in this case, .

Any bipartite graph is -colourable. This is an alternative definition of being bipartite.

Generally, a graph is -colourable precisely if it is -partite, meaning its vertices can be partitioned into disjoint sets such that all edges of the graph are between nodes in different parts.