Graph Theory

What is a graph?

A graph G = (V, E) consists of a finite set of vertices V and a set E of edges, where each edge is an unordered pair {u, v} (often written uv for ease) of distinct vertices u, v in V

What is the order of G?

|V| (no. of vertices)

What is the size of G?

|E| (no. of edges)

What is adjacent, neighbour and incident?

If e = uv is an edge, we say u is adjacent to v, that u is a neighbour of v (vice versa) and that u & v are incident

What is the neighbourhood and isolated?

The neighbourhood N(v) of a vertex v is the set of neighbours of v and the degree of v is deg(v) = |N(v)|, the no. of neighbours of v. We say that v is isolated if deg(v) = 0

What is a complement?

For any graph G, the complement of G is the graph Ḡ with V(Ḡ) = V(G) and with edge set

E(Ḡ) = {{u, v} : u, v in V(G), u =/ v & {u, v} not in E(G)}

That is, the edges of Ḡ are all pairs of distinct vertices which do not form an edge of G

What is the handshaking lemma?

For any graph G

2|E| = ∑_{v in V} deg(v)

What is a corollary of the handshaking lemma?

Every graph has an even no. if vertices of odd degree

What is a degree sequence?

The degree sequence of graph G is the sequence of all degrees of vertices in G (deg(v₁), deg(v₂), …, deg(v_n)) where v = {v₁, v₂, …, v_n} and these degrees are given in descending order so deg (v₁) >/ deg(v₂)

What are the min/max degrees?

The min degree of a graph g, denoted δ(G) is the smallest degree of a vertex of G

Similarly, the max degree, Δ(G) is the largest vertex

What is a regular graph?

If every vertex of a graph G has the same degree. So deg(u) = deg(v) for all u, v in V. G is k-regular if every vertex has degree k

What are isomorphic graphs?

G & H are isomorphic graphs if they have the same structure i.e. V(G) = V(H) and E(G) = E(H)

What is k_n?

The complete graph or clique on n vertices. There is an edge between every pair of vertices

What is p_n?

The path of length n; it has n + 1 vertices and n edges

What is c_n?

The cycle of length n; it has n vertices and n edges. Note c₃ = k₃ : the graph is also known as a triangle

What is a label-preserving subgraph?

H is a label-preserving subgraph of G if H is a graph with V(H) ⊆ V(G) and E(H) ⊆ E(G). We can form H from G by deleting vertices/edges. If so, we say H is spanning (spanning subgraph) if V(H) = V(G) (no vertices deleted)

What is a subgraph?

H is a subgraph of g if there is a label-preserving subgraph H’ of G for which H and H’ are isomorphic. If H’ is spanning then we say h is a spanning subgraph of G. We denote H is a subgraph of G by H ⊆ G

What is a copy of H in G?

A label-preserving subgraph H’ ⊆ G which is isomorphic to H

Let G be a graph with δ(G) >/ 2. Then…

G contains a cycle

For all natural numbers n, every graph on n vertices with at least n edges contains…

A cycle

Let xy be an edge in a graph of order n. if deg(x) + deg(y) > n, then…

G contains a copy of k₃

Let G be a graph of order n with δ(G) > n/2, then…

G contains a copy of k₃

What is Mantel’s Theorem?

Let G be a graph of order n. If |E(G)| > n²/4, then G contains a copy of k₃

What is a walk?

A walk W in a graph is an ordered sequence of vertices (v₀, v₁, …, v_k) s.t. v_i-1v₁ is an edge for any 1 \< i \< r. We say ‘a walk from x to y’ to mean a walk whose first vertex is x and whose final vertex is y. The length of a walk is the number of edges traversed

What does it mean if a walk is closed?

A walk W is closed if v₀ = v_r

What is a connected graph?

A graph is connected if for any 2 vertices u and v of G there is a walk in G from u to v

What is a connected component?

A connected component of G is a maximal connected subgraph of G, so 2 distinct vertices are in the same connected component iff there is a walk between them in G. Observe a graph has one connected component if it is connected

Let u, v be vertices of a graph G. Then there’s a path in G from u to v iff

There is a walk in G from u to v

A graph G is connected iff

For all vertices u, v in G, there is a path from u to v

Let G be a graph on n vertices with at most n - 2 edges. Then…

G is not connected

For every graph G, what properties always hold?

• For every vertex x in V(G), there is a walk in G from x to x, namely (x), with length 0

• For all x, y in V(G), if W = (v₀, v₁, …, v_l) is a walk from x to y of length l, then W = (v_l, v_l-1, …, v₀) is a walk from y to x of length l

• For all x, y, z in V(G), if W = (x, v₁, …, v_l-1, y) is a walk in G from x to y of length l and W’ = (y, u₁, …, u_k-1, z) is a walk in G from y to z of length k, then W ^. W’ = (x, v₁, …, v_l-1, y, u₁, …, u_k-1, z) is a walk in G from x to z of length l + k