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 ) is a pair of sets , where is the set of vertices (or nodes) and 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 .
- We can also denote the vertices of a graph as and its
edges as . The number of vertices, is the called
's
**order**, and the number of edges, is called 's**size**. - Since edges are ordered pairs,
indicates there is
an edge from to , but not necessarily from to
-- if so there must be an edge
in . When this
distinction is important, we have a
**directed graph**. In this course the edge relationship is usually symmetrical: there is an edge if and only if there is an edge . In this case the edge is in fact the set (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 has is called
the
**degree**of (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 and are
**connected**if there is a path beginning with and ending with . Graph is connected if every pair of vertices in is connected. - Graph is
**complete**if every vertex is a neighbour of every other vertex. Clearly a complete graph is also connected. If 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, , or order 4, , etc. - A colouring is an assignment of colours to a graph so that
- every vertex is assigned a colour.
- no two neighbouring vertices are assigned the same colour

- The chromatic number of graph , denoted , (that's the greek letter chi) is the minimum number of colours required to colour . It's easy to come up with an upper bound for , since you is certainly colourable if . Usually is less than , but in the case of a complete graph , .
- To prove that for a given graph , you need
to prove both that is
**not**colourable, and that**is**colourable.