Graph basics

Section 6.1 Graph basics

Definition 6.1.1. Graph.

A graph is an ordered pair

Γ = (V, E),

where

V

is a set of vertices and

E

is a set of edges, where edges are unordered pairs of distinct vertices. That is,

E \subseteq {{u, v} : u, v \in V} .

🔗

In order to simplify notation, we will write

u v

instead of

{u, v}

for an edge.

🔗

Remark 6.1.2.

🔗

There are many, many different formulations for the definition of a graph. Some definitions are suffiently relaxed that an edge can loop back from a vertex to itself — these are generally called loops. Likewise, edges can be defined as independent objects with endpoints, which allows for more than one edge to have vertices

u

and

v

as endpoints. We make the distinction that graphs which have loops or multiple edges are multigraphs. In fact some graph theorists extend the definition even further to allow edges to have more than two vertices

🔗

Example 6.1.3. The Petersen graph.

🔗

A famous example of a graph is the Petersen graph,

Π .

Here it is drawn with its vertex set consisting of the collection of subsets of size 2 of the set

{0, 1, 2, 3, 4},

with an edge between vertices if and only if they are disjoint as sets. This labeling of the Petersen graph is convenient for several application in algebraic graph theory.

🔗

Definition 6.1.4. Adjacent and incident.

🔗

Two vertices

v_{0}, v_{1} \in V (Γ)

are adjacent if and only if

v_{0} v_{1} \in E (Γ) .

An edge

e \in E (Γ)

is incident with a vertex

v_{0} \in V (Γ)

if and only if there is another vertex

v_{1} \in V (Γ)

such that

v_{0} v_{1} = e .

🔗

Definition 6.1.5. Vertex degree.

🔗

The degree of a vertex

v \in V (Γ)

is the number of vertices adjacent to

v;

that is,

d (v) = | {u \in V : u v \in E} | .

🔗

Another term for the vertex degree is valence, as borrowed from chemistry, and historically some authors have preferred

ρ (v)

to denote valence.

🔗

Definition 6.1.6. Subgraphs.

🔗

A graph

Γ^{'} = (V^{'}, E^{'})

is a subgraph of

Γ = (V, E)

if and only if

V^{'} \subseteq V

and

E^{'} \subseteq E .

The subgraph

Γ^{'}

is the subgraph of

Γ

induced by

V^{'}

if and only if

E^{'} = {u v \in E : u, v \in V^{'}} .

That is,

Γ^{'}

is an induced subgraph of

Γ

if and only if every edge of

Γ

between vertices of

Γ^{'}

is an edge of

Γ^{'} .

There are many competing notations for induced subgraphs, but we will denote the induced subgraph of

V^{'}

Γ

Γ [V^{'}] .

🔗

Example 6.1.7. Some subgraphs of the Petersen graph.

🔗

If we relabel the vertices of the Petersen graph

Π

\begin{aligned} v_{0} & = {0, 1}, & v_{1} & = {1, 2}, & v_{2} & = {2, 3}, & v_{3} & = {3, 4}, & v_{4} & = {0, 4}, \\ v_{5} & = {2, 4}, & v_{6} & = {0, 3}, & v_{7} & = {1, 4}, & v_{8} & = {0, 2}, & v_{9} & = {1, 3}, \end{aligned}

🔗

then the subgraph

Π [V^{'}]

induced by

V^{'} = {v_{0}, v_{2}, v_{3}, v_{7}, v_{8}}

has edge set

E^{'} = {v_{0} v_{2}, v_{0} v_{3}, v_{2} v_{7}, v_{3} v_{8}, v_{7} v_{8}},

highlighted in red.

🔗

Definition 6.1.8. Graph isomorphism.

🔗

Two graphs

Γ = (V, E)

and

Γ^{'} = (V^{'}, E^{'})

are isomorphic if there is a function

ϕ : V \to V^{'}

such that the following three conditions hold.

Injective: 🔗
If $v_{0}, v_{1} \in V$ with $v_{0} \neq v_{1},$ then $ϕ (v_{0}) \neq ϕ (v_{1}) .$
Surjective: 🔗
If $v^{'} \in V^{'},$ then there is some $v \in V$ such that $ϕ (v) = v^{'} .$
Graph Homomorphism: 🔗
$v_{0} v_{1} \in E$ if and only if $v_{0}^{'} v_{1}^{'} \in E^{'}$ with $ϕ (v_{0}) = v_{0}^{'}$ and $ϕ (v_{1}) = v_{1}^{'} .$

🔗

If such a function exists, we write

Γ ≅ Γ^{'} .

🔗

Each of these conditions independently are important, but their combination is essential in graph theory: a graph isomorphism is an adjacency-preserving bijection between vertex sets.

🔗

Definition 6.1.9. Graph automorphism.

🔗

Let

Γ = (V, E) .

A permutation

ϕ : V \to V

which satisfies condition (3) of the definition of Graph isomorphism is a graph automorphism. The set of all automorphisms of a graph

Γ

is denoted

Aut Γ .

🔗

Example 6.1.10. Isomorphism is not equality.

🔗

Consider the graphs

K_{4} = ({a, b, c, d}, {u v : u, v \in V, u \neq v})

🔗

and

K_{4}^{'} = ({v_{0}, v_{1}, v_{2}, v_{3}}, {v_{i} v_{j} : i, j \in {0, 1, 2, 3}, i < j}) .

🔗

Since

V (K_{4}) \neq V (K_{4}^{'}),

obviously

K_{4} \neq K_{4}^{'} .

However choosing any bijection

ϕ : {a, b, c, d} \to {v_{0}, v_{1}, v_{2}, v_{3}}

suffices to produce a graph isomorphism from

K_{4}

K_{4}^{'},

K_{4} ≅ K_{4}^{'}

🔗

Definition 6.1.11. Paths.

🔗

Suppose

Γ = (V, E)

is a graph and

u, v \in V .

A path between

u

and

v

is any sequence

(u = v_{0}, e_{1}, v_{0}, e_{2}, v_{1}, \dots, v_{n - 1}, e_{n}, v_{n} = v)

🔗

such that

e_{i} = v_{i - 1} v_{i}

for each

i \in {1, 2, \dots, n}

and

v_{i} \neq v_{j}

i \neq j .

This can also be called a

u, v

-path. A path containing

n

edges is a path of length

n .

🔗

Definition 6.1.12. Graph distance.

🔗

Let

Γ = (V, E)

be a graph and

v_{0}, v_{1} \in V .

The distance from

v_{0}

v_{1}

is the length of a shortest path between

v_{0}

and

v_{1} .

If no such path exists, the distance from

v_{0}

v_{1}

\infty .

Distance between

v_{0}

and

v_{1}

in the graph

Γ

is sometimes denoted

d_{Γ} (v_{0}, v_{1}),

which can be easily confused with the notation for degree.

🔗

Definition 6.1.13. Cycles in graphs.

🔗

A cycle is a sequence

(v_{0}, e_{1}, v_{0}, e_{2}, v_{1}, \dots, v_{n - 1}, e_{n}, v_{n} = v_{0})

🔗

such that

e_{i} = v_{i - 1} v_{i}

for each

i \in {1, 2, \dots, n}

and

v_{i} \neq v_{j}

i \neq j

except for

v_{0} = v_{n} .

A cycle containing

n

edges is an

n

-cycle, and is isomorphic to the cycle graph

C_{n} = (Z_{n}, {a b : a, b \in Z_{n}, a - b \equiv 1 \mod (n)} .

🔗

Example 6.1.14. Paths and a cycle in the Petersen graph.

🔗

It is easy to draw the Petersen graph with two distinct (and openly disjoint)

v_{0}, v_{3}

-paths, one highlighted in red and the other in blue. The union of the red and blue paths is a 9-cycle in

Π .

🔗

Definition 6.1.15. Connected graphs.

🔗

The graph

Γ

is connected if and only if for any two distinct vertices

v_{0}, v_{1} \in V

there is at least one

v_{0}, v_{1}

-path.

🔗

Definition 6.1.16. Components of a graph.

🔗

A subgraph

Γ^{'} = (V^{'}, E^{'})

of a graph

Γ = (V, E)

is a component of

Γ

if and only if

Γ^{'} = Γ [V^{'}]

and

Γ [V^{'} \cup {v}

is disconnected for any vertex

v \in V ∖ V^{'} .

Clearly, a connected graph has only one component.

🔗

Definition 6.1.17. Trees and forests.

🔗

A connected graph containing no cycles is called a tree. An arbitrary graph containing no cycles is called a forest. For a given graph

Γ = (V, E),

a forest

Φ = (V, E^{'})

where

E^{'} \subseteq E

is called a spanning forest. A spanning tree of a connected graph is defined analogously.

🔗

These are just a few of the basic definitions of graph theory. It is a subject which is very appealing for research as the problems are often visually interesting. Since problems in the field are very accessible, some mathematicians are mildly derogatory towards graph theory, calling the field “recreational mathematics.” If that is so, then the vast number of graph theorists are perhaps the luckiest of all mathematicians: their chosen field of research is seen to be fun and games by their colleagues!

🔗

All joking aside, graph theory and the larger discipline of combinatorics are deeply applicable fields. There are many pratical, real world problems which are modeled by discrete systems (rather than continuous systems, such as used in differential equations or traditional applied math courses), and graph theory techniques are often the best solution to these problems. So while combinatorics is not generally considered part of applied mathematics, it is very much applicable mathematics.

Prev Top Next