If you read the What is Graph ? page, you might have thougt 'Ohm.. it is interesting concept. it doesn't look as hard and boring as other mathematical topics'. and if you went through 'Terminology' page, 'Pretty many technical words.. but I think I can digest it to some degree', but Graph Theory is also a part (branch) of mathematics. The area is also using a lot of mathematical symbols and mathematical representations and you have to get familiar with those notations (representations) if you want to do serious study on this subject.

There are several different ways of representing a graph and you will see various different forms from different text books or papers etc. Some of the firm may look a little bit easier or more familiar and some of them may look pretty intimidating (daunting/scary) to you. Don't get scared away from this topic just because of those mathematical symbols, just try to pick up any form which would look the most familiar to you and search a lot of materials (books, web pages etc) that are using the same/similar form until you get fully familiar with the concept and then you can extend it to other forms of representation piece by piece.

Followings are several different forms of representation and this list will keep being extended as I come across more forms and find time for update.

The three examples below add information one step at a time. The first one only names the parts of a graph. The second one lists the vertices and the edges by name. The third one says which two vertices each edge connects, and that is the first form from which you can draw the graph. After the examples, I'll show how the same notation is extended for directed and weighted graphs, and how it turns into the matrices used on the following pages.

• Example 1 - Graph as a Pair of Sets
• Example 2 - Named Vertices and Edges
• Example 3 - Edges as Vertex Pairs
• Directed and Weighted Graph Notation
• From Set Notation to Matrices

Example 1 - Graph as a Pair of Sets

This would be the most simplest form of representation. It is also the form you will meet most often, because almost every definition and theorem in graph theory starts with it. The important point is that a graph is not a picture. It is two sets, and the picture is only one way to show them.

The meaning of this is as follows. It simply says "We have a graph called 'G' and the graph is made up of the vertice V and the edge E". It does not say anything about how many vertices are in the graph and how many edges are in the graph. But this presentation is still be widely used in pure theoretic text and it implies 'the theory (theorem, rules etc) is applied to any type of graph'.

The annotated version below labels each symbol in G = (V, E). G is the name of the graph, V is the set of all vertices, and E is the set of all edges.

Two more symbols usually come with this form. The number of vertices is written |V| and is called the order of the graph. The number of edges is written |E| and is called the size of the graph. Many texts use n = |V| and m = |E| as short names. When a theorem needs to talk about the sets of a particular graph G, you will also see V(G) and E(G).

• G = (V, E) is a pair of sets : V holds the vertices and E holds the edges. The order matters, so the vertex set is always written first.
• The form is general on purpose : It carries no count and no connection, so a statement written with it holds for every graph.
• |V| and |E| are the two basic counts : |V| is the order of the graph and |E| is its size.

Example 2 - Named Vertices and Edges

This has a little bit more information of the graph comparing to the first example. Now the two sets are written out, so you know that the graph has four vertices and four edges. But you still don't know which vertices an edge joins.

The meaning of this representation is as follows.

Does this have enough information with which you can draw a specific graph ?

Still No. It does not have the information on which edge is connecting which vertice. In order to draw a specific graph, you would need adjacent matrix or incidence matrix or you should use another form of representation.

The diagram below shows what the two sets give you. The vertices v₀ to v₃ sit in one box, and the edges e₀ to e₃ sit in another box as loose lines. No edge is attached to any vertex yet.

Let's count how many graphs fit this description. Suppose we only allow simple graphs, so there is no loop and no second edge between the same two vertices. Four vertices have 4 x 3 / 2 = 6 possible vertex pairs, and we have to choose 4 of them. That gives C(6, 4) = 15 different edge sets. So one line of Example 2 notation describes 15 different graphs, and even more if loops and parallel edges are allowed. Either an adjacency matrix or an incidence matrix removes this ambiguity. The incidence matrix also keeps the edge names, because each of its columns belongs to one edge.

• Named sets give the counts, not the connections : Here |V| = 4 and |E| = 4, but the edges are only labels.
• Many graphs share the same Example 2 description : With four vertices and four edges, 15 simple graphs fit it.
• One matrix is enough to fix the graph : An adjacency matrix or an incidence matrix records which vertices each edge joins, and you do not need both.

Example 3 - Edges as Vertex Pairs

Following is a form that contains enough information that you can at least draw a graph. (It is still missing some information about the direction of the edges, but at least you can draw a graph which is not 'directed' (non-directed graph). This type of definition goes as follows.

Detailed meaning of this definitiona can be illustrated as follows. As you see, you can come out with a complete graph (diagram) from the definition itself.

In the diagram below, each vertex pair in E becomes one line between two vertices. The bottom box shows the result: v₃ connects to all three other vertices, v₀ and v₁ are also joined to each other, and v₂ has only one edge.

In an undirected graph, the pair (v₀, v₁) and the pair (v₁, v₀) mean the same edge. For this reason, many texts write an undirected edge as a set, {v₀, v₁}, or simply as v₀v₁. The round brackets in this example are read the same way.

The pair list also gives you the degree of each vertex, which is the number of edges that touch it. Count how often each vertex appears in E. The result is deg(v₀) = 2, deg(v₁) = 2, deg(v₂) = 1 and deg(v₃) = 3. The sum is 8, which is twice the number of edges. This is always true, because each edge has two ends and adds 1 to the degree of each end. It is known as the handshaking lemma.

• A list of vertex pairs defines the graph completely : For an undirected graph without edge weights, V and the pair list E are all you need to draw it.
• Undirected pairs have no order : (v₀, v₁) and (v₁, v₀) are the same edge, which is why many texts use set brackets.
• The sum of all degrees is 2|E| : Here 2 + 2 + 1 + 3 = 8 = 2 x 4.

Directed and Weighted Graph Notation

Example 3 still leaves out two things that many real problems need. One is the direction of an edge, as in a one-way road or a data link that only sends one way. The other is a number on each edge, such as a distance, a cost or a channel gain. Both are added to the same G = (V, E) form with small changes.

For a directed graph, an edge is an ordered pair. The pair (v₀, v₁) means an edge from v₀ to v₁, and it is not the same edge as (v₁, v₀). Many texts call a directed edge an arc and write the arc set as A instead of E, so the graph becomes D = (V, A). If we read the four pairs of Example 3 as ordered pairs, every arc leaves from the first vertex of its pair. Each vertex then has two degrees. The out-degree counts the arcs that leave the vertex, and the in-degree counts the arcs that arrive. For this directed version, the out-degrees of v₀ to v₃ are 2, 1, 1 and 0, and the in-degrees are 0, 1, 0 and 3. Both lists add up to 4, the number of arcs.

For a weighted graph, a weight function is added to the pair: G = (V, E, w). The function w gives each edge a real number, and w(v_i, v_j) is the weight of the edge between v_i and v_j. Some texts write this weight as w_ij instead. An unweighted graph is the special case where every edge has the weight 1.

• Directed edges are ordered pairs : (v_i, v_j) points from v_i to v_j, and reversing the pair gives a different arc.
• A directed graph has two degrees per vertex : The sum of the out-degrees and the sum of the in-degrees are both equal to the number of arcs.
• A weighted graph adds a function, not a new set : G = (V, E, w) keeps V and E and puts one number on each edge.

From Set Notation to Matrices

Set notation is good for definitions, but you cannot compute much with it. To use linear algebra on a graph, we write the same information as a matrix. The four matrix pages in this section all start from the same idea, and the graph of Example 3 is a convenient case to see it.

The adjacency matrix A has one row and one column for each vertex. The element a_ij is 1 when v_i and v_j are joined by an edge, and 0 otherwise. For the graph of Example 3, the table below gives A. Because the graph is undirected, A is symmetric. The sum of each row is the degree of that vertex.

The other three matrices follow from the same edge list. The incidence matrix has one row per vertex and one column per edge, so it keeps the edge names e₀ to e₃. The degree matrix D is diagonal, and here D = diag(2, 2, 1, 3). The Laplacian matrix is L = D - A. The table below lists where each one is covered in detail.

• A matrix holds the same information as the pair list : For a simple undirected graph, the adjacency matrix and the edge list can each be rebuilt from the other.
• Row sums of A are the degrees : For Example 3 they are 2, 2, 1 and 3, the same numbers counted from the pair list.
• The matrix form lets you use linear algebra : Powers of A count walks, and the eigenvalues of L tell you about connectivity. The pages linked above work through both.