See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/357884617

Matrix Representation of Graph Theory with Different Operations

Article in IOSR Journal of Mathematics · January 2022

DOI: 10.9790/5728-1801010827

CITATIONS READS

2 5,424

4 authors, including:

Md Ashraful Islam Omar Faruk

Khulna University Dhaka International University
7 PUBLICATIONS 10 CITATIONS 7 PUBLICATIONS 17 CITATIONS

SEE PROFILE SEE PROFILE

Suman Kar
World University of Bangladesh
14 PUBLICATIONS 26 CITATIONS

SEE PROFILE

All content following this page was uploaded by Omar Faruk on 17 January 2022.

The user has requested enhancement of the downloaded file.

IOSR Journal of Mathematics (IOSR-JM)
e-ISSN: 2278-5728, p-ISSN: 2319-765X. Volume 18, Issue 1 Ser. I (Jan. – Feb. 2022), PP 08-27
www.iosrjournals.org

Matrix Representation of Graph Theory with Different

Operations
Md. Ashraful Islam1, Omar Faruk2* , Suman Kar3, Mohammad Shahidul Islam4
1
(Department of Computer Science and Engineering, Dhaka International University, Dhaka-1205, Bangladesh)
2
(Department of Civil Engineering, Dhaka International University, Dhaka-1212, Bangladesh)
3
(Basic Science Division, World University of Bangladesh, Dhaka-1205, Bangladesh)
4
(Department of Mathematics, Tejgaon College, Dhaka-1215, Bangladesh)

Abstract: Graph theory is one of the most important and basic topics of discrete mathematics in Mathematics.
In all sectors of science graph theory has a great impact. The most common use of graphs occurs in Physics and
Chemistry except Mathematics. It is also used in the modeling of Biology, Finance, and Computer science.
Basic concepts of graphs are discussed here with classification and figures. In this paper Historical background
of graphs, classification, matrix representation of graphs, different types of graph operations, isomorphism, and
some important theorems are briefly reviewed. Our main objective is to represent the graph theory in terms of
matrix. Future researchers will get a clear and visual concept on graph theory of discrete mathematics by this
paper.
Key Word: Graphs, Matrix Representation, Incidence matrix, Adjacency Matrix, Cut-Set Matrix, Circuit
Matrix, Graph operations.
---------------------------------------------------------------------------------------------------------------------------------------
Date of Submission: 01-01-2022 Date of Acceptance: 12-01-2022
---------------------------------------------------------------------------------------------------------------------------------------

I. Introduction
Graphs are mathematical structures used to model pair-wise relations between objects from a certain
collection. A graph consists of , a nonempty set of vertices, and , a set of edges. Each edge has
either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.
Vertices can be any abstract data type and can be presented with the points in the plane. These abstract data
types are also called nodes. A line or line segment connecting these nodes is called an edge. Again, more
abstractly saying, the edge can be an abstract data type that shows the relation between the nodes.
Graphs were first used as a purely mathematical way to solve a fun problem by Leonhard Paul Euler
(1707- 1783). Leonhard Paul Euler was a pioneering Swiss mathematician who spent most of his life in Russia
and Germany. Euler solved the first problem using graph theory and thereby led to the foundation of a very vast
and important field of graph theory. He created the first graph to simulate a real-time place and situation to solve
a problem which was then considered one of the toughest problems. The problem was ‘Konigsberg bridge
problem’. The Konigsberg bridge problem was originated in the city of Konigsberg, formerly in Germany but
now known as Kaliningrad and part of Russia, located on the river Preger. The city had seven bridges that
connected two islands with the main-land via seven bridges. People staying there always wondered whether was
there any way to walk over all the bridges once and only once. The below picture is the map of Konigsberg
during Euler's time showing the actual layout of the seven bridges highlighting the river Preger and the bridges.

Figure 1: Konigsberg’s seven bridges

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 8 | Page
 Matrix Representation of Graph Theory with Different Operations

In 1736 Euler came out with the solution in terms of graph theory. He proved that it was not possible to
walk through the seven bridges exactly one time. In coming to this conclusion, Euler formulated the problem in
terms of graph theory. He abstracted the case of Konigsberg by eliminating all unnecessary features. He drew a
picture consisting of dots that represented the landmasses and the line segments representing the bridges that
connected those landmasses. The resulting picture might have looked somewhat similar to the figure shown
below.

Figure 2: Euler’s Graph of Konigsberg bridge

This simplifies the problem to a great extent. Now, the problem can be merely seen as the way of
tracing the graph with a pencil without actually lifting it. One can try it in all possible ways but you will soon
figure out that it is not possible. But Euler not only proved that it is not possible but also explained why it is not
and what should be the characteristic of the graphs so that its edge could be traversed exactly once. He came out
with the new concept of the degree of nodes. The Degree of Node can be defined as the number of edges
touching a given node. Euler proposed that any given graph can be traversed with each edge traversed exactly
once if and only if it had zero or exactly two nodes with odd degrees. The graph following this condition is
called the Eulerian circuit or path. We can easily infer this theorem. Exactly two nodes are starting and ending
of your trip. If it has even nodes then we can easily come and leave the node without repeating the edge twice or
more. In the actual case of seven bridges of Konigsberg, once the situation was presented in terms of the graph
the case was simplified as the graph had just 4 nodes with each node having an odd degree. So, Euler concluded
that these bridges cannot be traversed exactly once. In 1840, August Ferdinand Mobius (1790–1868) gave the
idea of the complete graph and bipartite graph, and Kuratowski (1896 –1980) proved that they are planar by
means of recreational problems. Gustav Robert Kirchhoff (1824 –1887) developed the theory of trees in 1847 in
order to solve the system of simultaneous linear equations which give the current in each branch and around
each circuit of an electric network. Although a physicist, he thought like a mathematician when he abstracted an
electric network with its resistances, condensers, inductances, etc., and replaced it by its corresponding
combinatorial structure consisting only of points and lines without any indication of the type of electrical
element represented by individual lines. Thus, in effect, Kirchhoff replaced each electrical network with its
underlying graph and showed that it is not necessary to consider every cycle in the graph of an electric network
separately in order to solve the system of equations. Instead, he pointed out by a simple but powerful
construction which has since become a standard procedure that the independent cycles of a graph determined by
any of its "spanning trees" will suffice. A contrived electrical network, its underlying graph, and a spanning tree
are shown in the figure below.

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 9 | Page

 Matrix Representation of Graph Theory with Different Operations

Figure 3: Kirchhoff’s circuit

In 1852 Thomas Guthrie (1803–1873) found the famous four-color problem. In 1857 Arthur Cayley
(1821–1895) discovered the important class of graphs called trees in the very natural setting of organic
chemistry. He was engaged in enumerating the isomers of the saturated hydrocarbons , with a given
number of carbon atoms, as shown in the figure below.

Figure 4: Cayley’s isomers

Of course, Cayley restated the problem abstractly: find the number of trees with p points in which
every point has degree or . He did not immediately succeed in solving this and so he altered the problem
until he was able to enumerate: rooted trees (in which one point is distinguished from the others), trees with
points of degree at most , and finally the chemical problem of trees in which every point has degree or .
Jordan later (1869) independently discovered trees as a purely mathematical discipline. A game invented by Sir
William Rowan Hamilton (1805-1865) in 1859 used a regular solid dodecahedron whose vertices are labeled
with the names of famous cities. The player is challenged to travel "around the world" by finding a closed circuit
along the edges which passes through each vertex exactly once. Hamilton sold his idea to a toymaker in Dublin
for guineas. This was a shrewd move since the game was not a financial success. The figure of the graph is
shown below.

Figure 5: Hamilton’s dodecahedron toy

It took 200 years after Euler before the first book on graph theory was written. In 1936 a Jewish
Hungarian mathematician Denes Konig (1884 –1944) wrote the first book on graph theory which was originally
published in Leipzig, Germany. The name of the book was ‘Theorie der endlichen und unendlichen Graphen
(Theory of finite and infinite graphs)’. Another book named ‘Graph Theory’ was written by Frank Harary
(1921–2005) which was published in 1969. This book was considered the definitive textbook on the subject
worldwide and enabled mathematicians, chemists, electrical engineers, and social scientists to talk to each other.

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 10 | Page

 Matrix Representation of Graph Theory with Different Operations

Since then graph theory has developed into an extensive and popular branch of mathematics that has been
applied to many problems in mathematics, computer science, and other scientific areas.

II. Preliminaries
In this section, some definitions related to the graph theory have been discussed which are important
for representing our main objective in the later sections.
(1) Vertex: A vertex is a point where multiple lines meet. It is also called a node. Similar to points, a vertex is
also denoted by an alphabet.
Example: Here, the vertex is named as ‘a’.

(2) Edge: An edge is a mathematical term for a line that connects two vertices. Many edges can be formed from
a single vertex. Without a vertex, an edge cannot be formed. There must be a starting vertex and an ending
vertex for an edge.
Example: In the below graph and are the two vertices and the link between them is called an edge.

(3) Degree of a Vertex: Degree is defined for a vertex. It is the number of edges connected (coming in or
leaving out) to a vertex.
Example: Let us name the vertices in Graph, the vertices and have degree , the vertices and have
degree .

(4) Loops: In a graph, if an edge starts and ends on the same vertex, it is called a loop.
Example: In the Graph below vertex has a loop.

(5) Order of a Graph: The order of a graph is defined as the number of vertices present in the graph.
Example: The order of the graph below is

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 11 | Page

 Matrix Representation of Graph Theory with Different Operations

(6) Multiple Edges: In a graph, if two vertices are connected with more than 1 edge, it is called multiple edges.
Example: In the Graph below the vertices and have multiple edges.

(7) Region: Every planar graph divides the plane into connected areas called regions.
Example: The regions are shown in the graph below.

(8) Degree of the region: The degree of a bounded region is the number of edges enclosing the regions .
Example: In the graph below

(9) Diameter: The diameter of a graph is the length of the longest shortest path between any pairs of nodes in
the graph. It is denoted by
Example: In the graph below the diameter is ( to ).

(10) Cut Set of a Graph: Let be a connected graph. A subset of E is called a cut set of if
deletion of all the edges of from makes disconnect. If deleting a certain number of edges from a graph
makes it disconnected, then those deleted edges are called the cut set of the graph.
Example: Take a look at the following graph. Its cut set is .

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 12 | Page

 Matrix Representation of Graph Theory with Different Operations

After removing the cut set from the graph, it would appear as follows –

Similarly, other cut sets can disconnect the graph −

 – Smallest cut set of the graph.


(11) Null Graph: A graph that has no edges is called a null graph. The null graph of vertices is denoted by
.
Example:

(12) Pseudograph: A graph that contains loops or multiple edges or both is called a pseudograph.
Pseudograph simple graph multi-edge loop.
Example:

(13) Complete graph: A simple graph that contains exactly one edge between each pair of distinct vertices is
called a complete graph. The complete graph with n vertices is denoted by .

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 13 | Page

 Matrix Representation of Graph Theory with Different Operations

Example:

(14) Walk: A walk in a pseudograph is an alternating sequence of vertices and edges, beginning and ending
with a vertex, in which each vertex (except the last) is incident with the edge which follows and the last edge is
incident with the edge which precedes it. A walk is closed if the first vertex is the same as the last vertex
otherwise it is open.
Example: In the graph is an open walk. On the other hand, the walk
is closed.

(15) Path: A walk in which all vertices are distinct is called a path.
Example: In the graph the walk is a path.

(16) Trail: A walk in which all edges are distinct is called a trail.
Example: The walk in the graph is a trail.

(17) Circuit: A closed trail is called a circuit.

Example: In the graph the walk is a circuit.

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 14 | Page

 Matrix Representation of Graph Theory with Different Operations

(18) Cycle: A cycle is a closed walk (path) in which all vertices are distinct except first and last If a
graph consists of a single cycle, it is called a cycle graph. The cycle graph with n vertices is denoted by
Example:

(19) Wheel: By adding an additional vertex to the cycle , for and connecting this new vertex to each
of the n vertices in by new edges, we obtain a graph which is called wheel. It is denoted by .
Example:

(20) n-cube: The graph that has vertices representing the bit strings of length are called -dimensional
cube or -cube. It is denoted by .
Example:

(21) Weighted graph: A graph is said to be a weighted graph if each edge of is assigned a non-negative
number (weight, length, distance, cost, delay, probability). A weighted graph is therefore a special type of
labeled graph.
Example:

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 15 | Page

 Matrix Representation of Graph Theory with Different Operations

(22) Regular graph: A graph is regular if all the vertices of the graph have the same degree. In a regular graph
of degree , the degree of each vertex of is .
Example:

(23) Directed graph: A digraph or directed graph is a graph in which each edge of the graph has a direction.
Such an edge is known as the directed edge.

Example:

(24) Tree: A tree is a connected graph that contains no cycles. In a tree, every pair of points is connected by a
unique path.
Example:

(25) Spanning tree: A spanning tree for a graph is a sub-graph of which is a tree that includes every vertex
of .
Example:

(26) Euler graph: A connected graph is called an Euler graph if there is a closed trail that includes every
edge of the graph . An Euler path is a path that uses every edge of a graph exactly once. An Euler path starts
and ends at different vertices.
DOI: 10.9790/5728-1801010827 www.iosrjournals.org 16 | Page
 Matrix Representation of Graph Theory with Different Operations

Example:

(27) Hamiltonian Graphs: A connected graph is called a Hamiltonian graph if there is a cycle that includes
every vertex of and the cycle is called the Hamiltonian cycle. Hamiltonian walk in graph is a walk that
passes through each vertex exactly once.
Example:

(28) Isomorphism: Let and be two graphs. Then is said to be isomorphic

to if there is a one-to-one function from into such that
1) If is an edge in then is an edge in ,
2) Every edge in has the form for some edge in
If is isomorphic to then we denote this by .

If two graphs are isomorphic they must have:

i. the same number of vertices
ii. the same number of edges
iii. the same degrees for corresponding vertices
iv. the same number of connected components
v. the same number of loops
vi. the same number of parallel edges.

Example:

The number of vertices and edges of and are the same. Hence there may be an isomorphism between and
.
Let us define a mapping such that

Now
i. is an edge of G and is an edge of .
ii. is an edge of G and is an edge of .
iii. is an edge of G and is an edge of
iv. is an edge of G and is an edge of .
v. is an edge of G and is an edge of .
vi. is an edge of G and is an edge of .

Thus if is an edge of then is an edge of . Also, every edge in has the form
for some . Hence by the definition of isomorphism, the two graphs are isomorphic.

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 17 | Page

 Matrix Representation of Graph Theory with Different Operations

III. Main Results

Graph operations
(1) Conversion from Directed Graph to Undirected graph: This is the simplest conversion. A directed graph
has directions represented by arrows, in this conversion we just remove all the arrows and do not store the
direction information. Also, the graph remains unchanged in terms of its structure.
Example: The below image shows a conversion from a directed graph to an undirected graph.

(2) Conversion from Undirected Graph to Directed graph: This conversion gives a directed graph given an
undirected graph . It is the exact reverse of the above. The trick to achieving this is to add one edge for
each existing edge in the edge family . Once the extra edges are added, we just assign the opposite direction to
each pair of edges between connecting vertices.
Example: The below image shows a conversion from an undirected graph to a directed graph.

(3) Reversing a graph: Reversing a graph is an operation meant for directed graphs. To reverse a graph we
reverse the direction of the edges. The reverse graph has the same vertex set as the original graph.
Example: The below image shows reversing a graph.

(4) Deriving a Simple graph: The operation is to derive a simple graph out of any given graph. A simple graph
by definition must not contain any self-loops or multi edges. As we understand that a graph can contain loops
and multiple edges, this operation shall remove the loops and multiple edges from the graph to obtain a
simple graph.
Example: The below image shows deriving a simple graph from a graph .

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 18 | Page

 Matrix Representation of Graph Theory with Different Operations

(6) Delete Vertex: This operation changes the vertex set and the edge family of the graph.
Example: The below image shows deleting vertex of a graph .

(7) Contract Vertex: Contract vertex can be done by contracting two vertices into one. Also, it can be done by
contracting an edge. We cannot contract one vertex, for contraction we need a set of vertices, a minimum of
two. Contraction can only be done when there is an edge between the two vertices. The operation basically
removes all the edges between the two vertices.
Example: In the below illustration vertices are contracted and are also contracted.

(8) Delete Edge: Deleting an edge can be done by removing the connection between the given vertices.
Example: The below image shows deleting edge from a graph .

(9) Union of Graphs: The union of two graphs and is the union of their vertex sets and
their edge families. That means
Example: The below image shows a union of graph and graph .

(10) Disjoint union: When and are disjoint then the Union is referred to as disjoint Union and it is
denoted by .
Example: The vertex sets are disjoint in the two graphs.

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 19 | Page

 Matrix Representation of Graph Theory with Different Operations

(11) Intersection of Graphs: The intersection of two graphs and is the union of their
vertex sets and the intersection of their edge families. That means
Example: The below image shows an intersection of graph and graph .

(12) Difference of Graphs: The difference of two graphs and is the union of the vertices
of two graphs and and the edges in the difference are the difference of edges which is – . It is denoted
by – . The Graph Difference of any graph and itself is an empty graph which means – .
Example: The below image shows a difference between graph and graph .

(13) Graph Complement: The complement of graph is a graph that has the same vertices as but the
edges defined by two vertices in the complement are adjacent only if they are not adjacent in . It is
denoted by . The Graph complement is also called edge complement.
Example: The below image shows a complement of graph .

Matrix Representation of Graph theory

The graph can be represented in the form of the matrix. The matrices that can be formed by a graph are given
below.
1. Incidence Matrix
2. Adjacency Matrix
3. Cut-Set Matrix
4. Circuit Matrix
5. Path Matrix
(1) Incidence Matrix: An edge connected to a vertex is known as the incidence edge to that vertex. Let be a
graph with vertices, edges, and without self-loops. The incidence matrix of is an matrix
whose rows correspond to the vertices and the m columns correspond to edges such that

It is also called vertex-edge incidence matrix and is denoted by

Example: Consider the Graph below

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 20 | Page

 Matrix Representation of Graph Theory with Different Operations

The incidence matrix of is

(2) Adjacency Matrix: When two vertices are connected by single path then they are known as adjacent
vertices. If a vertex is connected to itself then the vertex is said to be adjacent to itself. Let be a graph with
vertices, edges. The adjacency matrix of is an matrix whose n rows correspond to the
vertices and the columns correspond to edges such that

Example: Consider the Graph below

The adjacency matrix of is

(3) Cut-Set Matrix: Cut set is a set of edges in a graph whose removal leaves the graph disconnected. Let be
a graph with edges and cutsets. The cut-set matrix of is a matrix with

Example: Consider the graph shown in the figure below

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 21 | Page

 Matrix Representation of Graph Theory with Different Operations

In the graph
The cut-sets are
.
Thus the cut-set matrices are given by

2.4 Circuit Matrix: Circuit is a close walk in which no vertex/edge can appear twice. Consider a loopless graph
which contains circuits. We enumerate the circuits of . The circuit matrix
of is an matrix where

Example: Consider the graph shown in the figure below

In the graph the circuits are . Hence the circuit matrix is

given by

(5) Path Matrix: Path is an open walk in which no vertex edge can appear twice. Let be a graph with m
edges, and and be any two vertices in . The path matrix for vertices and denoted by
where is the number of different paths between and , is defined as
DOI: 10.9790/5728-1801010827 www.iosrjournals.org 22 | Page
 Matrix Representation of Graph Theory with Different Operations

Clearly, a path matrix is defined for a particular pair of vertices, the rows in correspond to different
paths between and , and the columns correspond to different edges in .
Example: Consider the graph shown in the figure below

The different paths between the vertices and are , and

. The path matrix for is given by

Theorem 1 (HANDSHAKING THEOREM): If is an undirected graph with edges, then

Proof: Consider two vertices and in V. If then is contributed to for both

and . Thus every non self-loop edge contributes to the vertex degree sum. On the other hand, if
is a self-loop, then this edge contributes to the degree of . Therefore, each edge contributes
exactly to the vertex degree sum. This completes the proof.

Theorem 2 (EULER’S FORMULA): Let be a connected planar simple graph with edges and vertices.
Let be the number of regions in a planar representation of . Then .

Proof: First we specify a planar representation of . We will prove the theorem by constructing a sequence of
subgraphs , successively adding an edge at each stage. This is done using the following
inductive definition. Arbitrarily pick one edge of to obtain . Obtain from by arbitrarily adding an
edge that is incident with a vertex already in , adding the other vertex incident with this edge if it is not
already in . This construction is possible because G is connected. G is obtained after e edges are added. Let
and represent the number of regions, edges, and vertices of the planar representation of induced by
the planar representation of , respectively. The proof will now proceed by induction. The relationship
is true for because and .
Now assume that . Let be the edge that is added to to obtain . There are
two possibilities to consider. In the first case, both and are already in . These two vertices must be
on the boundary of a common region , or else it would be impossible to add the edge to
without two edges crossing (and is planar). The addition of this new edge splits R into two regions.
Consequently, in this case, and . Thus, each side of the formula relating
the number of regions, edges, and vertices increases by exactly one, so this formula is still true. In other words,
.
In the second case, one of the two vertices of the new edge is not already in . Suppose that ak+1 is in but
that is not. Adding this new edge does not produce any new regions, because must be in a region that
has on its boundary. Consequently, Moreover, and . Each side of
the formula relating the number of regions, edges, and vertices remains the same, so the formula is still true. In
other words . We have completed the induction argument. Hence,
for all . Because the original graph is the graph obtained after edges have been added. This proves the
theorem.

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 23 | Page

 Matrix Representation of Graph Theory with Different Operations

Theorem 3 (HALL’S MARRIAGE THEOREM): The bipartite graph with bipartition has
a complete matching from to if and only if for all subsets of .

Proof: We first prove the only if part of the theorem. To do so, suppose that there is a complete matching
from to . Then, if , for every vertex , there is an edge in connecting v to a vertex in .
Consequently, there are at least as many vertices in that are neighbors of vertices in as there are vertices in
. It follows that To prove the if part of the theorem, the more difficult part, we need to show
that if for all , then there is a complete matching from to . We will use strong
induction on to prove this.
Basis step: If , then contains a single vertex . Because , there is at least
one edge connecting and a vertex w0 . Any such edge forms a complete matching from to .
Inductive step: We first state the inductive hypothesis.
Inductive hypothesis: Let be a positive integer. If is a bipartite graph with bipartition and
, then there is a complete matching from to whenever the condition that for
all is met.
Now suppose that is a bipartite graph with bipartition and . We will prove
that the inductive holds using a proof by cases, using two cases. Case (i) applies when for all integers j with
the vertices in every set of j elements from are adjacent to at least elements of . Case
(ii) applies when for some j with there is a subset of j vertices such that there are exactly j
neighbors of these vertices in . Because either Case (i) or Case (ii) holds, we need only consider these cases
to complete the inductive step.

Case (i): Suppose that for all integers j with , the vertices in every subset of elements from are
adjacent to at least elements of . Then, we select a vertex and an element which
must exist by our assumption that . We delete v and w and all edges incident to them from
H. This produces a bipartite graph with bipartition Because the
inductive hypothesis tells us there is a complete matching from Adding the edge from v
to w to this complete matching produces a complete matching from to .

Case (ii): Suppose that for some j with , there is a subset of vertices such that there are exactly
neighbors of these vertices in . Let be the set of these neighbors. Then, by the inductive hypothesis, there
is a complete matching from to . Remove these 2j vertices from and and all incident edges to
produce a bipartite graph K with bipartition We will show that the graph satisfies the
condition for all subsets of . If not, there would be a subset of t vertices of
where – such that the vertices in this subset have fewer than t vertices of as
neighbors. Then the set of vertices of consisting of these t vertices together with the j vertices we
removed from has fewer than neighbors in , contradicting the hypothesis that for all
.
Hence, by the inductive hypothesis, the graph has a complete matching. Combining this complete matching
with the complete matching from to , we obtain a complete matching from to .
We have shown that in both cases there is a complete matching from to . This completes the inductive
step and completes the proof.

Theorem 5: Let be a graph with . Then the following are equivalent:

(1) T is a tree.
(2) T is acyclic and has exactly edges.
(3) T is connected and has exactly edges.
(4) T is connected and every edge is a cut-edge.
(5) Any two vertices of T are connected by exactly one path.
(6) T is acyclic and the addition of any new edge creates exactly one cycle in the resulting graph.

Proof: Assume is a tree. Then by definition, is acyclic, and the fact that it has edges.

( Since is acyclic, it must be a forest and we know . Since we assumed that has
edges, we must have and thus the number of components of is and thus must be
connected.

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 24 | Page

 Matrix Representation of Graph Theory with Different Operations

The fact that is connected is assumed from 3. Suppose we consider the graph
where . Then the number of edges in is . The graph contains n vertices and must still be
acyclic (that is a forest) and therefore Thus and e was a cut-edge.

Choose two vertices and in . The fact that there is a path between and is guaranteed
by our assumption that is connected. By way of contradiction, suppose that there are at least two paths from
to in . These two paths must diverge at some vertex and recombine at some other vertex . (See
below Figure) We can construct a cycle in by beginning at vertex w following the first path to and the
following the second path back to from .

Figure 6: The proof of requires us to assume the existence of two paths in graph connecting vertex
to vertex This assumption implies the existence of a cycle, contradicting our assumptions on .

By Definition removing any edge in this cycle cannot result in a disconnected graph. Thus no edges in the
constructed cycle in a cut-edge are contradicting our assumption on . Thus, two paths connecting and
cannot exist.

The fact that any pair of vertices is connected in implies is connected (i.e., has one
component). Now suppose that has a cycle (like the one illustrated in Figure above). Then it is easy to see
there are (at least) two paths connecting and contradicting our assumption. Therefore, is acyclic. The
fact that adding an edge creates exactly one cycle can be seen in the following way: Consider two vertices and
and suppose the edge is not in . We know there is a path

in T connecting and and it is unique. Adding the edge creates the cycle

so at least one cycle is created. To see that this cycle is unique, note that if there is another cycle present then it
must contain the edge Suppose that this cycle is

where there is at least one vertex not present in the set (otherwise, the two cycles are
identical). We now see there must be two disjoint paths connecting and namely

and

this contradicts our assumption on . Thus the created cycle is unique.

It suffices to show that T has a single component. Suppose not, there are at least two components
of . Chose two vertices and in V so that these two vertices are not in the same component. Then the edge
is not in E, and adding it to E cannot create a cycle. To see why not that if is the graph that results
from the addition of e then e is now a cut-edge. We see that e cannot lie on a cycle and thus the addition of this
edge does not create a cycle, contradicting our assumption on . Thus, must have a single component. Since it
is acyclic and connected hence is a tree. This completes the proof.

Theorem 6: Let be a non-empty, non-trivial connected graph . Then the following are equivalent:

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 25 | Page

 Matrix Representation of Graph Theory with Different Operations

(1) is Eulerian.
(2) The degree of every vertex in is even.
(3) The set E is the union of the edge sets of a collection of edge-disjoint cycles in .

Proof: Assume G is Eulerian then there is an Eulerian tour t of . Let v be a vertex in . Each time
is traversed while following the tour; we must enter by one edge and leave by another. Thus, v must have an
even number of edges adjacent to it. If is the initial (and final) vertex in the tour, then we leave in the very
first step of the tour and return in the last stage, thus the initial (and final) vertex of the tour must also have an
even degree. Thus every vertex has an even degree.

Since is connected and every vertex has an even degree, it follows that the degree of each vertex is
at least 2. By definition, must contain a cycle . If this cycle includes every edge in , then (3) is established.
Suppose otherwise. Consider the graph obtained by removing all edges in . If we consider as a subgraph
of , then each vertex in has exactly two edges adjacent to it. Thus if is a vertex in the cycle, then removing
the edges in that are adjacent to it will result in a vertex having fewer edges in than it did in . Since
we assumed that every vertex in had an even degree, it follows that every vertex in must also have an even
degree (since we removed) either or edges from each vertex in to obtain . We can repeat the previous
process of constructing a cycle in and if necessary forming Since there are a finite number of edges in ,
this process must stop at some point and we will be left with a collection of edge disjoint cycles
whose union is the entire edge set of .

Assume that is connected and that its edge set is the union of a collection of edge-disjoint cycles.
We proceed by induction on the number of cycles. If there is only one cycle, then we simply follow this cycle in
either direction to obtain a tour of . Now suppose that the statement is true for a graph whose edge set is the
union of edge disjoint cycles. We'll show that the statement is true for a graph whose edge set is composed
of edge disjoint cycles. Denote the cycles . A subgraph of composed of only
cycles will have m components with . Each component is composed of at most n edge
disjoint cycles and therefore applying the induction hypothesis, each has a tour. Denote the components
. The cycle shares one vertex in common with at least one of these components (and
perhaps all of them). Without loss of generality, assume that is a component sharing a vertex in common
with (if not, reorder the components to make this true). Begin following the tour around until we
encounter the vertex that component and share. At this point, break the tour of and begin
traversing until (i) we return to or (ii) we encounter a vertex that is shared by another component
(say ). In case (i), we complete the tour of and necessarily we must have completed a tour of the entire
graph since it is connected. In case (ii) we follow the tour of until we return to and then continue
following until either case (i) occurs or case (ii) occurs again. In either case, we apply the same logic as
before. Since there are a finite number of components, this process will eventually terminate with case (i), we
complete the tour of and thus we will have constructed a tour of the entire graph. This theorem is illustrated
in the figure below. This completes the proof.

IV. Conclusion
In this work, graphs are discussed with simple examples and theorems to explain easily. The historical
background of graphs states that many important topics of science could not possible to explain without the help
of graph theory. Many practical problems can be easily represented in terms of graph theory. This may help
future researchers to proceed further.

References
[1]. Discrete Mathematics and its applications - Kenneth H. Rosen (7th edition)
[2]. Discrete Mathematics - Prof. Dr. Md. Ayub Ali and Prof. Dr. M.F Rahman
[3]. Graph theory - Harary

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 26 | Page

 Matrix Representation of Graph Theory with Different Operations
[4]. Graph Theory with Applications - J.A. Bondy and U.S.R. Murty
[5]. Graph Theory- Reinhard Diestel
[6]. Introduction to Graph Theory - Douglas West (2nd edition)
[7]. Modern Graph Theory- B. Bollobas, Springer-Verlag.
[8]. Graph theory - Keijo Ruohonen
[9]. Complex Graphs and Networks - Fan Cheung and Linyuan Lu.
[10]. Graphs, Networks and Algorithms - Dieter Jungnickel,Vol. 5, Springer Verlag, Berlin.
[11]. An Inside Guide To Algorithms - Siegel and Cole.
[12]. Graph Theory -Tero Harju, Department of Mathematics, University of Turku, Finland.
[13]. https://en.wikipedia.org/wiki/Graph_theory
[14]. https://www.tutorialspoint.com/graph_theory/index.htm
[15]. http://mathforum.org/isaac/problems/bridges2.html
[16]. http://www-history.mcs.st-andrews.ac.uk/Biographies/Euler.html

DOI: 10.9790/5728-1801010827 www.iosrjournals.org 27 | Page

View publication stats