Graph

A linear graph or simply a graph $G=(v,e)$, consists of a set of objects, $V=\{v_1,v_2,v_3,\ldots\}$ called vertices, and another set $E=\{e_1,e_2,e_3,\ldots\}$ called edges such that each edge, $e_k$, is identified with unordered pair of vertices.

Following is an example of a simple graph:

In the above example, the vertices set is: $V=\{A,B,C,D\}$, and the edges set is: $E=\{1,2,3,4,5\}$

Some Terms in Graph Theory

Following are some terms widely used in graph theory:

Self loop

An edge having the same vertex as both its end vertices is called a self loop.

Following is an example:

In the above example, edge 1 is a normal edge and edge 2 is a self loop with the same end vertices.

Parallel edges

If more than one edge is associated with a given pair og vertices, such edges are referred to as parallel edges.

Given below is an example of a graph showing parallel edges:

In the above example, edges 3 and 4 are examples of parallel edges.

Question: Discuss the gamous Koinsberg bridge problem and give a solution OR Discuss one real life applications of graph theory.

Finite and infinite graph

If in a graph the number of vertices and edges are finite then it is called a finite graph otherwise it is called an infinite graph.

Type	Graph
Finite
Infinite

Incidence

When a vertex $v_i$ is an end vertex of same edge $E_j$, then $v_i$ and $E_j$ are said to be incident with each other.

In the following example, 3 is incident on B and C.

Adjacency

Two non-parallel edges are said to be adjacent if they are incident on a common vertex.

In the above example, 3&5 are non-adjacent due to a parallel edge between them. Other than that, all other edge pairs are adjacent to each other.

Degree of a vertex

The no. of edges incident on a vertex $v_i$ with self loop counted twice is called the degree $d(v_i)$ of a vertex.

In the above example, following are the degrees:

• $d(A)=2$
• $d(B)=2$
• $d(C)=2$
• $d(D)=1$

Isolated vertex

A vertex having no incident edge is called an isolated vertex. In the following example, C is an isolated vertex.

Pendant vertex

A vertex of degree 1 is called a pendant vertex or end vertex.

In the above example D is a pendant vertex.

Regular graph

A graph in which all the vertices are of equal degree is called a regular graph. Following is an example of a regular graph:

Theorem 1

The number of vertices of odd degree in a graph is always even.

Let us consider vertices with odd degree and even degree seperately. Then, the total number of degrees in a graph can be expressed as follows:

$$\begin{align} \sum_{i=1}^{n}{d(v_i)}=\sum_{\textnormal{even}}{d(v_j)}+\sum_{\textnormal{odd}}d(v_k) \end{align}$$

We know, the total degree of a graph can be obtained by the number of edges ($2\times\textnormal{edges}$). Therefore equation $(1)$ can be written as:

$$\begin{align} 2\times e=\sum_{even}{d(v_j)}+\sum_{odd}{d(v_k)} \end{align}$$

Where, $e$ is the number of edges.

The first expression on the right hand side is even, (being the sum of even numbers). The left hand side is also the sum of even degrees, which is also even. Thus equation $(2)$ can be expressed as follows:

$$\begin{align*} \ &\textnormal{even}=\textnormal{even}+\sum_{odd}{d(v_k)}\\ \Rightarrow\ &\textnormal{even}-\textnormal{even}=\sum_{odd}{d(v_k)}\\ \Rightarrow\ &\sum_{odd}{d(v_k)}=\textnormal{even} \end{align*}$$

The subtraction of one even number from another even number results in an even number. Therefore the theorem that, the number of vertices of odd degree in a graph is always even, holds true.

Isomorphism

Two graphs $G$ and $G'$ are said to be isomorphic if there is one-to-one correspondence between their vertices and their edges such that incidence relationship is maintained.

Thus for two isomorphic graph, it must have:

1. Same number of vertices
2. Same number of edges
3. An equal number of vertices with a given degree

In the following examples, $G_1$ and $G_2$ are isomorphic graphs:

Label	Graph
$G_1$
$G_2$

Example 1: "The criteria for isomorphism in the definition is insufficient." Justify this with an example.

Considering two graphs:

Graph having vertices set, $V_1=\{A,B,C,D,E,F\}$ be named $G$, and $V_2=\{Q,R,S,T,U,V\}$ be named $G'$.

According to the formal definition, both $G$ and $G'$ are isomorphic because:

1. They have equal number of vertices
2. They have equal number of edges
3. They have equal number of vertices with a given degree

The vertex $D$ in $G$ must correspond to the vertex $S$ in $G'$, as both their degree is 3. $W$ is associated with two pendant vertex whereas $S$ is associated with one pendant vertex, thus $G$ and $G'$ are not really isomorphic.

Sub-graph

A graph $g$ is said to be a subgraph of a graph $G$, if all the vertices and all the edges of $g$ are in $G$ and each edge of $g$ has the same end vertex in $G$.

For example, in the following, $g$ is a subgraph of $G$:

Label	Graph
$G$
$g$ (sub-graph)

Characteristics of sub-graph

• Every graph is its own sub-graph
• A sub-graph of a sub-graph of $G$ is also a sub-graph of $G$
• A single vertex of $G$ is also a sub-graph of $G$
• A single edge of $G$ along with its end vertices is also a sub-graph of $G$.

Operations on Graphs

Union

The union of two graphs, $G_1=(v_1,e_1)$, and $G_2=(v_2,e_2)$ is anothe graph, $G_3=(v_3,e_3)$, whose vertex set $v_3=v_1\cup v_2$, and edge set is $e_3=e_1\cup e_2$.

Following is the example of graphical union:

Label	Graph
$G_1$
$G_2$
$G_3=G_1\cup G_2$

Intersection

The intersection of two graphs $G_1=(v_1,e_1)$ and $G_2=(v_2,e_2)$, is another graph $G_3=(v_3,e_3)$, whose vertex set, $v_3=v_1\cap v_2$, and edge set is, $e_3=e_1\cap e_2$.

Following is the example of graphical intersection:

Label	Graph
$G_1$
$G_2$
$G_3=G_1\cap G_2$

Ring sum

The ring sum of two graphs $G_1=(v_1,e_1)$, and $G_2=(v_2,e_2)$, is another graph $G_3=(v_3,e_3)$, written as $G_3=G_1\oplus G_2$ whose vertex set $v_3=v_1\cup v2$, and edge set having those edges that are either in $G_1$ or in $G_2$ but not in both.

Label	Graph
$G_1$
$G_2$
$G_3=G_1\oplus G_2$

Fusion

A pair of vertices $(a,b)$ in a graph are said to be fused if the two vertices are replaced by a single new vertex such that every edge that was incident on either $a$ or $b$ or both are now incident on the new vertex.

Considering the following graph:

In the above graph when $B$ and $D$ are fused, we get the following, where edge 6 forms a self-loop and edge 2 and 4 are parallel.

Decomposition

A graph $G$ is said to have been decomposed into two sub-graphs $g_1$ and $g_2$ such that:

$$g_1\cup g_2=G;\\ g_1\cap g_2=\text{Null}$$

Example:

Label	Graph
$G$
Decomposed part
Final graph

Matrix Representation of a Graph

Incidence matrix

Let $G$ be a graph, with $n$ vertices, $e$ edges, and no self loops, then incidence matrix is an $n\times e$ matrix, $A=[a_{ij}]$, whose $n$ rows corresponds to $n$ vertices, and $e$ columns correspond to $e$ edges.

The following holds true:

• $a_{ij}=1$, if $j^{\text{th}}$ edge is incident on $i^{\text{th}}$ vertex
• $a_{ij}=0$, otherwise

Considering the following example:

Incidence matrix of the above graph:

$$\begin{matrix} &&1&2&3&4&5&6&7&8\\ \\ A&&1&0&0&0&0&0&0&0\\ B&&1&1&0&1&0&1&0&0\\ C&&0&1&1&0&0&0&0&0\\ D&&0&0&1&1&1&0&0&0\\ E&&0&0&0&0&1&1&1&1\\ F&&0&0&0&0&0&0&1&1\\ \end{matrix}$$

Characteristics

1. The number of 1s in a row gives the degree of the corresponding matrix.
2. Every edge is on exactly two vertices, hence every column has exactly two 1s.
3. A row with all 0s corresponds to an isolated vertex.
4. A column of single 1s would represent a self loop.
5. Two identical columns represent parallel edges.

Adjacency matrix

The adjacency matrix of a graph $G$ with $n$ vertices and no parallel edges is an $n\times n$ matrix $X=[a_{ij}]$, whose elements:

• $x_{ij}=1$, if there is an edge between $i^{\text{th}}$ and $j^{\text{th}}$ vertex
• $x_{ij}=0$, otherwise

Considering the following example:

Adjacency matrix of the above graph is:

$$\begin{matrix} &&A&B&C&D&E&F\\\\ A&&0&1&0&0&0&0\\ B&&1&0&1&1&1&0\\ C&&0&1&0&1&0&0\\ D&&0&1&1&0&1&0\\ E&&0&1&1&0&0&1\\ F&&0&0&0&0&1&0\\ \end{matrix}$$

Characteristics

1. The diagonal elements are zero if there are no self loop.
2. The number of 1s in a row or column gives the degree of that vertex.
3. There are no provision for parallel edges because that information cannot be stored in the matrix.
4. A row or column of all 0s correspond to an isolated matrix.
5. A matrix of all zeros represent a null graph.

Example 2: Draw a graph corresponding to the following matrix:

$$\begin{matrix} &&A&B&C&D&E\\\\ A&&0&1&0&0&0\\ B&&1&0&1&1&0\\ C&&0&0&0&0&0\\ D&&0&1&0&0&0\\ E&&0&1&0&0&0\\ \end{matrix}$$

The graph represented by the above matrix is:

Circuit matrix

Let the number of different circuits in a graph $G$ be $q$ and the number of edges in $G$ be $e$, then the circuit matrix $B=[b_{ij}]$ is a $q\times e$ matrix whose elements are:

• $b_{ij}=1$, if the $i^{\text{th}}$ circuit includes $j^{\text{th}}$ edge
• $b_{ij}=0$, otherwise

Considering the following example of a graph:

The above represented in circuit matrix will be:

$$\begin{matrix} &&1&2&3&4&5&6&7&8\\\\ C_1&&0&1&1&1&0&0&0&0\\ C_2&&0&0&0&1&1&1&0&0\\ C_3&&0&1&1&0&1&1&0&0\\ C_4&&0&0&0&0&0&0&1&1\\ \end{matrix}$$

Characteristics

1. The number of 1s in a row denotes the number of edges participating in the circuit.
2. A column of all zeros denotes an edge which is not part of any circuit.
3. A single 1 in a row denotes a self loop.
4. Two graphs $G_1$, and $G_2$ are isomorphic if they have the same circuit matrix.
5. A column of all 1s denotes an edge which is a part of all circuits.

Path matrix

A path matrix for a specific pair of vertices say $(x,y)$, and is written as $p(x,y)=[p_{ij}]$, where the number of rows denotes the different available paths between $x$ and $y$, and columns represent the edges.

• $p_{ij}=1$, if $j^{\text{th}}$ edge lies in $i^{\text{th}}$ path
• $p_{ij}=0$, otherwise

The same vertex cannot be travelled twice.

Considering the example for a following graph:

The path matrix between $A$ and $D$ is:

$$\begin{matrix} &&1&2&3&4&5&6&7&8\\\\ P_1&&1&0&0&0&1&1&0&0\\ P_2&&1&1&1&0&0&0&0&0\\ P_3&&1&0&0&1&0&0&0&0\\ \end{matrix}$$

Characteistics

1. A column of all zeros, represents an edge which is not a part of any edge of the paths.
2. A column of all 1s represent an edge which is a part of all the paths.
3. The number of 1s in a row give the path length.
4. It only works for two given vertices.
5. Path matrix cannot be attained if both vertices source and destination are the same.

Sub Sections of a Graph

Following are the different sections in which a graph can be sub-divided into:

Walk

A walk is defined as a finite alternating sequence of vertices and edges beginning and ending with vertices such that each edge is incident with vertices preceeding and following it. No edge appears more than once in a walk.

A single vertex cannot be a part of a walk.

Open and closed walk

If it is possible for a walk to begin and end at the same vertex such a walk is called a closed walk. A walk that is not closed is called an open walk.

In the above example, transversing AECDB is an open walk., while AEBDCA is a closed walk.

Another example of walk is, AEDCE

Path

An open walk in which no vertex appears more than once is called a path. The number of edges in the path is called length of the path.

In the above example, AECDB is a path with a path length of 4.

All paths are a walk, but all walks are not a path.

A path has to be an open walk.

Circuit

A closed walk in which no vertex except the initial and final appears more than once is called a circuit.

In the above example, AECBDA is a circuit.

A self loop is the smallest circuit.

A circuit has to be a closed loop.

Connected and disconnected graph

A graph $G$ is said to be connected if there is atleast one path between every pair of vertices otherwise it is disconnected.

The above graph is a connected graph as all vertices are joined by atleast one edge.

Theorem 2

A simple graph with $n$ vertices and $k$ components, can have atmost $E_l$ edges, where, $E_l$ is:

$$E_l=\frac{(n-k)(n-k+1)}{2}$$

Proof

Let the number of vertices in each of the $k$ components be $n_1,n_2,\ldots,n_k$. Thus we have:

$$\begin{align} n_1+n_2+\ldots+n_k=n \end{align}$$

We can derive:

$$\begin{align} \sum_{i=1}^k(n-1)=n-k \end{align}$$

Squaring both sides we get:

$$\begin{align*} \Rightarrow\sum_{i=1}^k(n-1)^2&=(n-k)^2\\ \Rightarrow\sum_{i=1}^k n^2-2\sum_{i=1}^kn_i+k+\text{Cross Term}_+&=n^2-2nk+k^2\\ \Rightarrow \sum_{i=1}^kn^2&\le n^2-2nk+k^2+2n-k \end{align*}$$

After removing the non-negative cross term, we get:

$$\begin{align} \sum_{i=1}^kn^2\le n^2-(k-1)(2n-k) \end{align}$$

The maximum number of edges in the $i^\text{th}$ component is $\frac 12 n_i(n_i-1)$. Therefore, the maximum number of edges in the graph $G$ is equal to:

$$\sum_{i=1}^k\frac 12n_i(n_i-1)=\frac 12\sum_{i=1}^kn^2-\frac 12\sum_{i=1}^kn_i$$

From eq. $(5)$ we can write:

$$\begin{align*} E_l&\le \frac12\{n^2-(k-1)(2n-k)-n\}\\ &\le\frac12(n^2-2nk+k^2+2n-k-n)\\ &\le\frac12\{(n-k)^2+(n-k)\}\\ &\le\frac12(n-k)(n-k+1) \end{align*}$$

Thus, taking the maximum value from above, we can state a simple graph with $n$ vertices and $k$ components can have at most, $E_l$ elements as stated below:

$$\begin{align} E_l=\frac12(n-k)(n-k+1) \end{align}$$

Hence the theorem.

Forms of Graph

There are two most popular forms of graphs: Euler Graph, and Hamiltonian Circuit.

Euler Graph

If some closed walk in a graph contains all the edges of the graph then the walk is called an Euler Line, and the graph is called an Euler Graph.

Each vertex should have even degree to allow entry as well as exit points.

The above is an example of an Euler Graph, transversing ACBADEA.

Hamiltonian Circuit

A Hamiltonian Circuit is a connected graph and is defined as a closed walk that traverses every vertex exactly once except of course the starting vertex at which the walk also terminates.

It is not necessary to travel all edges in Hamiltonian Circuit.

There are two Hamiltonian Circuits in the above graph: ACBA and ADEA.

Tree

A tree is a connected graph without circuit. In the following example: $G_1$, and $G_2$ are trees:

Label	Graph
$G_1$
$G_2$

Theorem 3

A tree with $n$ vertices, has $n-1$ edges.

Proof

The theorem will be proved by induction on the number of vertices.

No. of vertices	No. of edges
$n=1$	$e=0$
$n=2$	$e=1$
$n=3$	$e=2$

Let us assume that the theorem holds true for $n=k$ vertices, with the maximum number of edges amounting to $e=k-1$. If we can prove that the theorem holds true for $n=k+1$ then it holds true for all values of $n$.

Let us consider a tree $T$ with $k+1$ vertices. In $T$, let $e_m$ be an edge that connects two vertices $v_i$ and $v_j$. Division of $e_m$ will disconnect the tree into two subtrees, $t_1$ (with $p$ vertices), and $t_2$ (with $q$ vertices). There cannot be any other path between $v_i$ and $v_j$, otherwise it will form an circuit.

Both $t_1$ and $t_2$ has less than or equal to $k$ vertices hence the theorem should hold true for for both $t_1$ and $t_2$.

We know:

$$\begin{align} p+q=k+1 \end{align}$$

Subtree $t_1$ has $p-1$ edges, and subtree $t_2$ has $q-1$ edges. Therefore, the total number of edges is the sum of edges of $e_{t_1}+e_{t_2}$ and $1$ from the edge where the tree was broken into two subtrees. Therefore total edges in tree $T$, $e_T$ is:

$$\begin{align*} e_T&=e_{t_1}+e_{t_2}+1\\ &=(p-1)+(q-1)+1\\ &=(p+q)-2+1\\ &=(p+q)-1\\ &=k+1-1&&[\because e_T=n-1=(k+1)-1]\\ &=k \end{align*}$$

Therefore, the maximum number of edges in a tree, with $n=k+1$ vertices is $k$.

Definitions Used to Characterize Graphs

Distance

In a connected graph $G$, the distance $d(v_i,v_j)$ between two of its vertices $v_i$ and $v_j$ is the length of the shortest path between $v_i$ and $v_j$, i.e., the number of edges in the shortest path between $v_i$ and $v_j$. Example:

In the above graph, the distance between $A$, and $E$ is: $d(A,E)=2$.

Metric Function

A function $f(x,y)$, is called a metric function, if it satisfies the following three conditions:

1. Non-negativity: $f(x,y)\ge0$, and $f(x,y)=0, \text{if } x=y$
2. Symmetry: $f(x,y)=f(y,x)$
3. Triangular Inequality: $f(x,y)\le f(x,z)+f(z,y)$, for any $z\in\R$

Example 3: Show with an example that distance in a graph is a metric function.

In order to show that distance is a metric function, the graph must exhibit: non-negativity, symmetry and triangular inequality.

Considering the following example:

1. Non-negativity: The number of edges in a path between two vertices can never be negative but can be zero if source and destination vertices are same. Example: $d(A,D)=2$, and $d(D,D)=0$

2. Symmetry: $d(A,D)=2, d(D,A)=2$

3. Triangular inequality: We have: $d(A,D)=2, d(A,E)=2, d(E,D)=1$. Therefore the following holds true:

   $$\begin{align*} d(A,D)&\le d(A,E)+d(E,D)\\ \Rightarrow2&\le2+1\\ \Rightarrow2&\le3 \end{align*}$$

   Which holds true, hence distance exhibits triangular inequality.

Eccentricity

The eccentricity $E(v)$ of a vertex $v$ in a graph $G$ is the distance from $v$ to $v_i$, the farthest distance from $v$ in $G$, as shown by the following equation:

$$\begin{align*} E(v)=\text{max } d(v,v_i); && v_i\in G \end{align*}$$

In the above example, the eccentricity are as follows:

• $E(A)=E(C)=E(H)=E(G)=4$
• $E(B)=E(F)=E(E)=3$
• $E(D)=2$

Eccentricities are to be calculated for edges not shared with pendant vertices.

Center

A vertex with minimum eccentricity in a graph $G$, is called its center.

In the above example the vertex with the lowest eccentricity is $D$. Therefore, $D$ is the center vertex.

Theorem 4

Every tree has either one or two center.

Considering the following graph:

Proof

The maximum distance from a given vertex $v$ to any vertex $v_i$ can only occur if $v_i$ is a pendant vertex. With this observation we delete all the pendent vertex from $T$ to obtain $T'$

The vertices in $T'$ have one less eccentricity than $T$. Thus the center or centers of $T$ are still center or centers in $T'$.

We continue this process of deleting pendent vertices to obtain $T'',T''',\ldots$, until we are left with a tree with vengle vertex (one center), or a tree with two vertices and an edge, (two center), hence the theorem.

After two successful removal of pendant vertex, we get, $T'$, and $T''$as:

Label	Tree
$T'$
$T''$

Radius

The eccentricity of the center is called the radius of the tree. Following is the example of a graph:

In the above graph, $C$ and $D$ are the centers, and their eccentricity are $E(C)=E(D)=2$, therefore, the radius is 2.

Diameter

The diameter of a tree $T$ is the length of the longest path in $T$, i.e., the path with maximum eccentricity.

In the above diagram, the length of the longest path is 3, so diameter of the tree is 3.

It is not necessary that the diameter of a tree is always twice of its radius.

Rooted tree

A tree in which one vertex is distinguishable from all the other vertices is called a rooted tree.

In the above diagram, vertex $A$ is a root vertex.

Binary rooted tree

A special class of rooted tree called binary rooted tree in which exactly one vertex is of degree two, and the remaining are of degree one or three.

The above is a binary rooted tree.

Example 4: If there are total $9$ vertices in a binary rooted tree, then how many vertices are of degree $1$?

We know:

$$\begin{align*} p&=\frac{n+1}2\\ &=\frac{9+1}2\\ &=5 \end{align*}$$

Where, $p$ is the number of pendant vertices, and $n$ is the total number of vertices.

Spanning tree

A tree $T$ is said to be spanning tree of a connected graph $G$, if $T$ is a subgraph of $G$ and $T$ contains all vertices of $G$. Spanning tree is also called a skeleton.

Following is an example of a graph $G$ and its spanning tree $T$:

Label	Diagram
$G$
$T$

Distance between spanning tree:

The distance between two spanning trees $T_i$ and $T_j$ of a graph $G$ is defined as the number of edges present in $T_i$ but not in $T_j$. It is written as $d(T_i,T_j)$.

Considering the following example

Label	Diagram
$G$
$T_i$
$T_j$

In the above graph and trees:

$$d(T_i,T_j)=2\\ d(T_j,T_i)=2$$

Example 5: Show with an example that distance between spanning trees is a metric function.

Considering the example used in the above pictures:

Non-negativity:

The number of edges present in one tree but not in the other tree cannot be a negative number, but a minimum of $0$ as in $d(T_i,T_j)=0, \text{if } T_i=T_j$.

Symmetry:

As in the above example, the number of edges not found in one tree of a graph, but found in the other tree of the same graph, in order to determine the distance, and vice versa. Therefore, the distance in two trees will be the same with respect to both the trees, hence they are symmetric.

$$d(T_i,T_j)=d(T_j,T_i)$$

Triangular inequality:

Considering another tree $T_k$ of the graph $G$ as:

For triangular inequality the following condition must hold true:

$$\begin{align*} d(T_i,T_j)&\le d(T_i,T_k)+d(T_k,T_j)\\ \Rightarrow2&\le 2+2\\ \Rightarrow2&\le 4 \end{align*}$$

Since the above condition holds true, therefore triangular inequality satisfies.

Minimal Spanning Tree

A spanning tree with the smallest weight in a weighted graph is called a shortest spanning tree or minimal spanning tree.

There are two ways to find minimal spanning tree:

1. Prim's algorithm
2. Kruskal's algorithm

Prim's algorithm

This algorithm is used to find the shortest spanning tree of a graph $G$ with $n$ vertices.

Steps

1. Draw $n$ isolated vertices and label them, $v_1,v_2,v_3,\ldots v_n$.

2. Tabulate the given weights of the edges of $G$ in an $n\times n$ matrix. (set the diagonals as empty and non-existing direct edges as infinity ($\infin$)).

3. Start from vertex $v_i$ and connect to its nearest neighbour (i.e., choose the smallest entry in $i^\text{th}$ root).

4. Repeat Steps (5,6), untill $\bold{n-1}$ edges have been selected.

5. Consider the previous selected row(s) and the currently selected row and choose the next smallest weight in the selected rows.

6. While considering the smallest weight, neglect those edges who have been already selected or those edges which forms a circuit.

7. Exit when all rows have been selected.

Example 6: Find minimal spanning tree using Prim's algorithm for the following graph, where the edge labels denote their weights.

Matrix tabulation

$$\begin{matrix} &A&B&C&D&E&F\\ A&-&7&6&1&\infty&\infty\\ B&7&-&8&\infty&\infty&\infty\\ C&6&8&-&5&3&\infty\\ D&1&\infty&5&-&4&5\\ E&\infty&\infty&3&4&-&2\\ F&\infty&\infty&\infty&5&2&-\\ \end{matrix}$$

From the above matrix we can find out that, the minimum spanning tree is:

Minimum spanning weight, $w_m$:

$$\begin{align*} w_m&=7+1+4+3+2\\ &=17 \end{align*}$$

Example 7: Find minimal spanning tree using Prim's algorithm for the following graph, where edge label denote the weight.

$$\begin{matrix} &A&B&C&D&E&F\\ A&-&2&2&\infty&\infin&\infin\\ B&2&-&3&6&2&\infin\\ C&2&3&-&5&\infin&3\\ D&\infin&6&5&-&4&1\\ E&\infin&2&\infin&4&-&\infin\\ F&\infin&\infin&3&1&\infin&- \end{matrix}$$

From the above matrix we can find out that the minimum spanning tree is:

Minimal spanning weight, $w_m$ is:

$$\begin{align*} w_m&=1+3+2+2+2\\ &=10 \end{align*}$$