Combinatorics: What Are Graphs?

Introduction to Graph Theory

So, what is graph theory. We'll first look at what a graph is :

Graph

The graph I'm talking about is not

or

It's

Most graphs have only at most one edge connecting two vertices for simplicity. However, graphs that do not satisfy this property is called a multigraph. Rarely, I graph will be a multigraph, so unless I say so, from now on, each graph will be simple, i.e. have only at most one edge connecting two vertices.

Notation and Terms

A cycle of a graph is a sequence of vertices and edges such that the first vertex is connected to the second, the second is connected to the third, ..., and the last vertex is connected back to the first.

A graph is called acyclic if it doesn't contain a cycle.

The degree of a vertex is the number of edges joining from it.

A graph is connected if there exists a sequence of vertices for every pair of points, starting from the first vertex in the pair to the last vertex in the pair, so that every two vertices are connected.

A tree is an acyclic connected graph.

Review

A graph is a way of encoding relationships between objects in a mathematically rigorous way. That relationship could be between people, ideas, objects, or anything else that have relationships between them. These items in the graph are called vertices (or nodes) and the connections between them are called edges.

The set of vertices in a graph is denoted by the capital letter $V$. The vertices are often denoted with subscripts $v_1, v_2$ etc, where each $v_i \in V$.

The set of edges in a graph is denoted by the capital letter $E$. Since an edge represents the connection between a pair of vertices $v_i$ and $v_j$, we often denote the edges as these pairings $(v_1,jv_j)$, where $a \neq b$, since we don't allow edges from a vertex to itself. And since each edge is formed of a pair of elements from $V$, we can say that $E\subset V\times V$ (where $V\times V$ is the set of pairings of elements in $V$).

With all this in hand, we can say that a Graph $G=(V,E)$ is a specific arrangement of vertices $V$ and edges between those vertices $E$. Conceptually, this means a graph is a set of points (vertices) with a bunch of lines (edges) drawn between the points (vertices).

We will now define some useful terms for describing aspects of graphs.

• adjacent: $v_1\sim v_2$: Two vertices $v_1,v_2$ are adjacent (written as $v_1\sim v_2$) in graph $G$, if the graph has an edge between them. This can be denoted mathematically by saying $(v_1,v_2)\in E$.
• neighbors: The neighbors of a vertex $v$ are all vertices adjacent to it. This is also described as the set vertices that $v$ has edges to.
• degree: The degree of a vertex $v$ is the number of neighbors of the $v$. This is also described as the number of vertices that $v$ is adjacent to.

A path is a sequence of vertices $v_0,v_1,\dots,v_k$ such that $v_i\sim v_{i+1}$ for all $i$ and no vertex is visited twice. A cycle is like a path but with $v_k\sim v_0$. Formally, a cycle is a sequence $v_0,\dots,v_k$ such that $v_0,\dots,v_k$, $v_1,\dots,v_k,v_0$, $v_2,\dots,v_k,v_0,v_1$, etc., all form paths. The length of a path is the number of edges ($k$), and the length of a cycle is also the number edges ($k+1$).

A graph is connected if for every two vertices there exists a path from one to the other. Otherwise, it's disconnected and thus consists of several connected components. The distance between any two vertices in a connected graph is the length of the shortest path from one to the other.

An orientation of a graph is an assignment of a direction to each vertex of a graph. A graph with an orientation is called a directed graph. They behave a lot differently from normal graphs: for example a normal graph can be connected but it can have an orientation in which it's disconnected.