Graph definitions

The intuitive notion of a graph is a drawing of (possibly labeled) nodes (often circles) with edges connecting some of them. Graphs turn out to be a model that many problems can be translated to, and often solved. You've already seen a special case of a graph, since a tree is an acyclic, connected graph with one node distinguished as the root (see definitions below).

Here are some formal definitions:

• A graph (denoted $G$) is a pair of sets $(V,E)$, where $V$ is the set of vertices (or nodes) and $E$ is the set of edges. Vertices are usually the elements of the problem we're interested in. Each edge connects two vertices, so it can be represented as a pair $(v_1, v_2)$.
• We can also denote the vertices of a graph $G$ as $V(G)$ and its edges as $E(G)$. The number of vertices, $\vert V(G)\vert$ is the called $G$'s order, and the number of edges, $\vert V(E)\vert$ is called $G$'s size.
• Since edges are ordered pairs, $(v_1, v_2)$ indicates there is an edge from $v_1$ to $v_2$, but not necessarily from $v_2$ to $v_1$ -- if so there must be an edge $(v_2, v_1)$ in $E$. When this distinction is important, we have a directed graph. In this course the edge relationship is usually symmetrical: there is an edge $(v_1, v_2)$ if and only if there is an edge $(v_2, v_1)$. In this case the edge is in fact the set $\{v_1, v_2\}$ (since sets have no order), and we have an undirected graph. A vertex may not have an edge to itself (unless we have a pseudograph).
• When two vertices share an edge they are ``adjacent'' (or ``neighbours''). The number of neighbours vertex $v$ has is called the degree of $v$ (for a directed graph we have in-degree and out-degree). A path is a list of vertices where each pair of vertices that are adjacent in the list are also adjacent in the graph.
• A circuit is a path that begins and ends on the same vertex without repeating any edges. A cycle is a path that begins and ends on the same vertex and doesn't repeat any vertices (and usually includes at least three vertices).
• Vertices $v_1$ and $v_2$ are connected if there is a path beginning with $v_1$ and ending with $v_2$. Graph $G$ is connected if every pair of vertices in $G$ is connected.
• Graph $G$ is complete if every vertex is a neighbour of every other vertex. Clearly a complete graph is also connected. If $G$ is a complete, undirected graph, how many edges does it have? It turns out that two complete graphs of the same order (same number of vertices) are equivalent (isomorphic, which is defined later), so it makes sense to talk about the complete graph of order 2, $K_2$, or order 4, $K_4$, etc.
• A colouring is an assignment of colours to a graph so that
  1. every vertex is assigned a colour.
  2. no two neighbouring vertices are assigned the same colour
  Usually we represent the colours by small integers. If it is possible to colour a graph with $k$ colours, we say the graph is ``$k$ colourable.'' If you know that it's possible with colour a graph with $k$ different colours, then you can certainly colour it with more than $k$ colours: being $k$ colourable doesn't require that all $k$ colours are used, only that $k$ colours are enough.
• The chromatic number of graph $G$, denoted $\chi(G)$, (that's the greek letter chi) is the minimum number of colours required to colour $G$. It's easy to come up with an upper bound for $\chi(G)$, since you $G$ is certainly $k$ colourable if $k$ $=$ $\vert V(G)\vert$. Usually $\chi(G)$ is less than $\vert V(G)\vert$, but in the case of a complete graph $G$, $\chi(G)$ $=$ $\vert V(G)\vert$.
• To prove that $\chi(G)$ $=$ $k$ for a given graph $G$, you need to prove both that $G$ is not $(k-1)$ colourable, and that $G$ is $k$ colourable.