Graph (graph theory)

This is an AoPSWiki Word of the Week for Jan 3-9

In graph theory, a graph is a set of vertices (or points) that are connected by a number of edges (which are not necessarily straight). Note that this number can be zero, in which case no points are connected. Formally, a graph $G$ is a pair, $G = (V, E)$ , of a set $V$ of vertices together with a subset $E$ of pairs of members of $V$ .

Properties and Subobjects

A walk is a way to start at any one vertex and travel through the entire graph. A path is a walk that cannot go through any vertex more than once, and a path is a walk that cannot go through any edge more than once. A cycle is a path which starts and ends at the same point. The number of edges coming out of any one vertex is called the degree of the vertex.

Types of Graphs

Complete Graph

A complete graph (or clique) is a graph in which every pair of points is connected. The clique with $n$ vertices is called $K_n$ .

Null Graph

The null graph (or independent set) is the opposite of the complete graph. A null graph is simply a scatter plot of points (which are the vertices) with no edges connecting them.

Connected graph

A graph is called connected if any two vertices can be connected by a path. That is, there are no isolated vertices with no paths coming from them, nor are there closed sub-graphs which are not connected by an edge anywhere.

Planar Graphs

A graph is said to be planar if it can be drawn in a plane with no intersecting edges. For example, $K_1,K_2,K_3,$ and $K_4$ are planar.

In a planar graph, we can define faces of the graph, or the smallest regions bounded by edges. (An alternate definition is the regions bounded by edges which do not have any edges going through them.) Note that the area outside the planar graph is also a face, called the unbounded face. The degree of the face is the number of edges that bound the face. (Note that the same term is used for vertices, which can become confusing)

All planar graphs have dual graphs, which involve turning the planes of one graph into vertices, and the vertics into planes, with edges connecting if two planes are adjacent. The dual of the dual of a graph is returns the original graph.

An interesting result is Euler's Polyhedral Formula, which states that in a planar graph with $V$ vertices, $E$ edges, and $F$ faces, then $V-E+F=2$ The proof of this is simple using induction, but the derivation of the formula is much trickier.

Other interesting results for planar graphs are that:

$E\le 3V-6$
if the the sum of the degrees of the faces of the graph is $F$ , then $F\le \frac{2}{3}E$ .

Bipartite graph

A graph is called bipartite if its vertex set can be split into two disjoint subsets such that no edge exists within each subset. A graph is bipartite if and only if it has no odd cycles, which is related to the Two Color Theorem. Bipartite graphs have many applications including matching problems.

Euler Trail

A Euler trail is a graph where it is possible to form a trail which uses all the edges. A Euler trail has at most two vertices with odd degrees. The sum of all the degrees of the vertices equals twice the number of edges in the graph.

Trees

A tree is a graph which does not have any sub-graphs which are cycles.

Hypergraph

A hypergraph is an extension of the concept of a graph where the edges can encompass more than two vertices, and essentially become sets themselves. Hypergraph theory is often difficult to visualize, and thus is often studied based on the sets that make it up.

Page

Toolbox

Search