Problem 29: Graph Theory Revisited

Index

A graph is a geometry in which every line contains exactly two points.

Definition. A graph, G = (V,E) consists of a finite set of vertices V, and a finite set of edges, E. Each edge connects an unordered pair of vertices An unordered pair of vertices means that (v',v'') = (v'',v') ; the edge that connects each of these ordered pairs is the same.

We will look at graphs in relation to some of the properties of geometries that we have already studied, while also looking at a few new ideas.

One thing that makes a graph different from most of the other geometries that we have studied so far is that it is possible to have mulitiple edges or loops (i.e., two vertices can be joined by more than one edge). Often a graph that allows multiple edges is referred to as a real graph. A graph without multiple edges is a simple graph. The graphs we will look at for the remainder of this section will be simple graphs.

For any given graph G = (V,E), where V = V(G) denotes the set of vertices (points) and E = E(G) the set of edges (lines),we define its complement such that and any edge (x,y) is in E'(G) if and only if (x,y) is not in E(G).

Let's look at an example of all of the simple graphs on four vertices:

Notice that each graph is the same color as its complement (so the complement of (c) is (h) and visa-versa, for example). Graph (g) is its own complement!

Any other simple graph drawn on 4 vertices, while it may appear different from one of these, is really just an isomorphic copy of one of the 11 graphs above. We have already seen the concept of an isomorphism for many other geometries, but lets define it again in reference to graphs.

Definition. Two graphs G = (V,E) and G' = (V',E') are isomorphic if there exists a bijective mapping F from V -> V' such that for every two vetices x, y in V, the edge (x,y) is in E if and only if ( F(x), F(y)) is in E'.

The properties of isometries are the same as all the other geometries we have seen. For example, all incidence relations must be preserved in an isomorphism.

Now, lets define the degree of a vertex v to be the number of lines with which v is incident.

A degree sequence of a graph G is the sequence of degrees of the vertices arranged in non-decreasing order.

For example, the degree sequence of (h) above is 2222 and the degree sequence of (i) is 1223. From this it is easy to see that these two graphs are not isomorphic.

In general, if two graphs are isomorphic, then they must have the same degree sequence (note that the converse of this is not always going to be true! - see if you can find a conterexample).

The sum of all the degrees of our vertices is two times the number of edges (this is true because we count each edge twice as each edge lies on two vertices). It follows then that in a graph, the sum of the degree sequence must be even!

Let's continue on to examine some other properties of graphs.

Definition. A walk is a sequence (x0,e1,x1,e2, ... , xk-1, ek, xk), where xi is in V(G) and ei is in E(G) in which x0,x1, ... , xk are vertices and ei is an edge from xi - 1 -> xi (i = 1,2, ..., k). The length of our walk is k.

A walk is a trail if there are no repeated edges.

A walk is a path if there are no repeated vertices. An example of a path through all four vertices above is (h).

A walk is a cycle if all vertices and edges are distinct except x₀ = x_k. Graph (f) above contains a cycle through 3 points.

If there is a walk that contains two vertices then there is a path between those vertices as well.

In a graph G, x is connected to y if and only if there exists a path from x to y, in which case we say x ~ y.

Lemma. Connectedness is an equivelance relation. x ~ x (this is trivial) x ~ y => y ~ x (this is also trivial) x ~ y, y~ z => x ~ z

A graph is spanned by the equivalence classes of the connectedness relation. Each class is called a connected component of the graph.

A graph is connected if it has exactly one connected component.

Definintion: A complete graph Kn on n vertices is a graph with all possible edges; every vertex is joined to every other vertex by a single edge.

Graph (k) above is the complete graph on 4 vertices.

The number of edges of a complete graph on n vertices is always . Do you see why?

A tree is a connected graph with no cycles. Graph (g) above is an example of a tree. Any tree will have at least two vertices of degree 1 (these will be the "endpoints").

Theorem: A tree with n vertices will have n - 1 edges.

Let's give a quick proof of this theorem. We will use induction on n, the number of vertices. The theorem obviously holds for n = 1 because we will always have 1 - 1 = 0 edges. Let's assume that our theorem holds true for n - 1 > 0. We will now show that it is true for a tree H with n vertices. Starting with H, we will remove one vertex with degree 1 (we know that at least two of these vertices exist). Thus, we must also remove the one edge that is incident with it. Now we are left with vertices V(H) - {v}, which will still be connected and acyclic because for any two vertices x and y in V(H) - {v}, the path that joins them did not pass through v. So H - v is a tree on n - 1 vertices. Thus, by our hypothesis, this tree has n - 2 edges. Thus, our entire graph H has n - 2 + 1 = n - 1 edges.

It is also easy to show by induction that a connected graph with n vertices and n - 1 edges will always be a tree.

We will now define one more type of graph that has many interesting properties. We will see some later.

Definintion: A graph G is bipartite if for vertex classes V1 and V2, and each edge of a vertex of V1 is joined to a vertex of V2. (note that no two vertices in V1 are connected and the same holds for V2 ) The graph is a complete bipartite graph if, in addition to begin bipartite, it contains all possible edges from V1 to V2

For more practice with the basic concepts of graph theory before you begin on the problems below, revisit this tutorial.

PROBLEM 29: (a) Give an example of two graphs, both being connected, having the same degree sequence, and the same list of lengths of cycles that are still not isomorphic. (b) Let G be a graph of n vertices, m edges and k components. Prove that G contains at least m - k + n = c cycles. (Hint: Prove this by induction on m) (c) For a tree on n vertices, n > 3, find the greatest number of vertices of degree greater than 2. (d) Which trees are complete bipartite graphs? Solutions

References: Personal notes.