Graph Theory

|G|

Order, no. vertices

||G||

Size of G, number of edges

Notation for an edge between x and y

xy (or yx)

Vertices x and y are adjacent if

xy is an edge in G

Two edges are adjacent if

They share an end

u-v walk

a sequence of vertices starting with u and ending with v, so that consecutive vertices in the walk are adjacent

Trail

A walk where no edge is repeated

Path

A walk where no edge or vertex is repeated

Open walk

A walk where the start and end are different

Circuit

A closed trail

Cycle

A circuit with no repeated vertex except the first & last

Eulerian graph

A graph with a circuit containing every vertex and edge (no repeated edges)

Degree

The number of edges incident to a vertex in a graph deg(v)

Eulerianity conjecture: A graph is Eulerian if and only if

It is connected and even

In an even graph, any trail that is not closed

can be extended

G’ = (V’, E’) is a subgraph of G if

V’ is a subset of V and E’ is a subset of E

G’ is an induced subgraph of G if

Every edge E connected to V’ in V is included in E'

result of G-U (U is a set of vertices)

G[V\U]

result of G-F (F is a subset of edges)

(V, E\F)

Result of G + F (F is a subset of edges)

(V, E U F)

3 key properties of connectedness

1. If u and v are connected, the v and u are connected

2. Every vertex v is connected in G to itself

3. If u is connected to v, and v to w, then u is connected to w

Semi-Eulerian

There exists an open trail (walk w/ no repeated edges) containing all edges and vertices

A graph is semi-Eulerian if and only if… (2 conditions)

It is connected and has exactly two odd vertices

Connected component

Maximal connected subgraph

Hamiltonian cycle

A circuit visiting each vertex exactly once

Hamiltonian path

An open walk (path) visiting each vertex exactly once

Hamiltonian graph

Graph with a Hamiltonian cycle (circuit that visits each vertex once)

Semi-Hamiltonian

Graph with a Hamiltonian path (path that visits each vertex once)

Let G be a graph with n>=3 vertices. G is Hamiltonian if for every vertex of G we have deg(v)…

deg(v) >= n/2

Ore’s theorem. G is Hamiltonian if for every pair of non-adjacent vertices v, w of G we have…

deg(v) + deg(w) >= n

The closure of a graph C(G) is obtained by

repeatedly joining pairs of non-adjacent pairs whose degree sum is at least n

Optimality of condition: d_k <= k < n/2 →

d_n-k >= n - k

Hamiltonian-connected

For every two vertices, u, v of G, there is a u-v Hamiltonian path

A vertex v of connected graph G is a cut vertex if

G-v is not connected

If G is a connected graph with no cut-vertices then G²

G² is Hamiltonian-connected

If G is Hamiltonian, then G is (connectivity)

G is 2-connected

u-B fan

given vertex u and vertices in set B, each pair of these paths only chare u in common

Isomorphic graphs

There is a bijection between the graphs

Graph property

A class, C, of graphs closed under isomorphism

Graph invariant

A map that assigns equal values to isomorphic graphs. ex. f(G) = |G|

Every graph has a unique _____ ___ ___ , whish is a _____ _____

decreasing degree sequence, graph invariant

2-switch (w/ edges uv and wx)

Delete edges uv and wx from G and add edges uw and vx

2-switch equivalent

G ~₂ G’ if G’ can be obtained from G by a sequence of 2-switched

Forest

A graph with no cycles

Tree

connected forest

||T|| (number of edges in a tree)

|T| - 1 (number of vertices - 1)

A graph is a tree if and only if

Every two vertices are connected by a unique path

Leaves

vertices of a tree with degree 1

How many leaves does every tree have?

At least 2

If v is ANY vertex, then T - v is a… (T is a tree)

Forest

T-v is a tree if an only if v is a

v is a lead

If F is a forest with components, ||F|| =

||F|| = |F| - k

A subgraph H of G is spanning if

V(H) = V(G)

If G is a connected graph, then ||G|| >=

||G|| >= |G| - 1

An edge e is a bridge if

G-e has more components than G

A graph G is nonseparable if (2 things)

It is connected & has no cut vertices

A block of a graph is

A maximal nonseparable subgraph

Two distinct blocks can share how many vertices?

At most one

The block-cut graph of a connected graph G is a

Tree (non-connected is a forest)

If G is Hamiltonian, then it has no

no cut-vertices

A graph is edge-nonseparable if (2 things)

It is connected and contains no bridge

If e = uv is a bridge, then at least one of u, v is

a cut vertex

A graph G is k-connected if: (2 things)

1. |G| > k

2. G-S is connected for every S in V with |S| < k

The connectivity of G is denoted by:

kappa(G)

A graph G is l-edge connected if: (2 things)

1. |G| > 1

2. G-F if connected for every F in E with |F| < l

edge-connectivity if denoted by:

lambda(G)

What if F called if G - F is disconnected? (F is a subset of edges)

edge cut

What is S called if G-S is disconnected? (S is a set of vertices)

separating or vertex cut

A graph is 2-connected iff it has

an open ear decomposition

A graph is 2-edge-connected iff it has

a closed ear decomposition

If F is a minimal edge-cut then G_F

has exactly 2 components

relationship between min degree/connectivity/edge-connectivity? (Whitney inequalities)

kappa(G) <= lamba(G) <= delta(G)

If G is k-connected and v is a vertex then G-v is

(k-1) connected

Notation for edge-contraction of G along e is

G/e = (V/e,E/e)

Menger’s vertex/set:

The maximum size of a collection of pairwise disjoint A-B paths is equal to the minimum size of an A-B separating set.

Menger’s vertex/vertex:

Let u,v be non-adjacent vertices. The maximum size of a collection of pairwise internally disjoint u-v paths is equal to the minimum size of a set separating u and v.

Menger’s vertex/global:

A graph with at least k+1 vertices is k-connected if and only if for every pair of distinct vertices u and v there is a collection of k internally disjoint u-v paths.

Two paths are edge-disjoint if

They do not share any edges

A u-v edge separating set is a set X in Edges such that

There are no uv paths in G-X

Menger’s edge/vertex:

The maximum size of a collection of pairwise edge disjoint u-v paths is equal to the minimum size of a u-v edge separating set.

Menger’s edge/global:

G is l-edge connected iff for all distinct vertices u, v there are l edge disjoint u-v paths in G.

A graph is k-regular if

for all vertices, deg(v) = k

A graph G is bipartite if we can

partition V into U and W (partite sets) so that every edge joins a vertex of U with a vertex of W

Every subgraph of a bipartite graph is

is bipartite

The disjoint union of bipartite graphs is

bipartite

A graph G is bipartite iff

we can “color” the vertices with two colors so that adjacent vertices receive different colors

A graph is bipartite if and only if it contains no

odd cycles