Title Graph Theory.pdf ✅

Graph Theory Graph: A graph G = (V,E) is a mathematical structure consisting of two sets, a non empty set V known as the vertex set and a set E known as the edge set. The elements of V and E are called vertices and edges respectively. Precisely V and E are also denoted as V (G) and E(G) respectively. Trivial Graph: A graph with single vertex and no edges is known as trivial graph. Null Graph: A graph for which edge set is empty is called null graph. Loop: An edge whose both the end points are same is known as a loop. Isolated vertex: A vertex which is not the end vertex of any edge is known as an isolated vertex. Parallel Edges or Multiple Edges: If two or more edges have the same end vertices are known as parallel edges or multiple edges. Simple Graph: A graph without loops or parallel edges is called simple graph. Adjacent vertices: The vertices which are joined by an edge are known as adjacent vertices and the adjacent vertices are called neighbors. Here edge e6 is a loop, e2 and e3 are multiple edges, v5 is an isolated vertex. 1
Incidence of a vertex and edge: If a vertex v is an end point of edge e then v is said to be incident on e. e and v are called incident to each other. Degree of a vertex: A degree of a vertex v in a graph G is defined as number of edges incident on v plus twice the number of loops. The degree of a vertex v is denoted by d(v) or dG(v). Pendent vertex: A vertex of degree 1 is called a pendent vertex. Odd & Even vertex: A vertex of a graph is called odd or even depending on whether its degree is odd or even. For the graph G shown in the following figure, we have d(v1) = d(v2) = d(v4) = 2 d(v3) = 3 d(v5) = 1 and d(v6) = 0. Theorem: For any graph G with e edges and n vertices v1, v2, . . . , vn the sum of degrees of vertices of a graph is twice the number of edges. Proof: Since each edge has two end points, each edge will precisely contribute 2 to the sum of degrees. Moreover each loop will also contribute 2 to the sum of degrees. Hence, Pn i=1 d(vi) = 2e. Theorem: For any graph G there is an even number of odd vertices. Proof: Let A and B be the set of even vertices and odd vertices respectively of graph G. Then for each a ∈ A, d(a) is even. This implies that P a∈A d(a) is even. Now by first theorem of graph theory we have X a∈A d(a) + X b∈B d(b) = 2e. Thus P b∈B d(b) = 2e − P a∈A d(a) which is even being difference of two even numbers. As all the terms in P b∈B d(b) are odd, the number of elements in B must be even. Thus for G there is an even number of odd vertices. Regular graph: A graph is said to be regular if all of its vertices have equal degree. If for every vertex v of a graph G, d(v) = k then that graph is known as k-regular. Complete graph: A complete graph is a simple graph in which every pair of vertices is joined by an edge. 2
We also note that a complete graph with n vertices is (n − 1)-regular. A complete graph on n vertices is denoted by Kn. In the following figure, the complete graphs on two, three, four and five vertices are shown. Bipartite graph: Let G be a graph with vertex set V . If V can be partitioned into two subsets such that V = V1 ∪ V2 and each edge of G has one end vertex in V1 and other end vertex in V2 then V is called bipartition of G and G is called a bipartite graph. Complete Bipartite graph: A complete bipartite graph is a simple bipartite graph with bipartition V = V1 ∪ V2 such that every vertex in V1 is joined to every vertex of V2. If V1 has m-vertices and V2 has n-vertices then such complete bipartite graph is denoted by Km,n. The complete bipartite graph K1,n is known as a Star graph. Here some complete bipartite graphs are shown. A directed edge (or arc) is an edge whose one end vertex is designated as the ‘tail’ and other end vertex is designated as the ‘head’. An arc is said to be directed from ‘tail’ to ‘head’. A multiarc or multiple arc is a set of two or more arcs having the same head and tail. A graph whose every edge is directed is called a directed graph or digraph. A graph which contains directed as well as undirected edges is called partially directed graph. 3
The underlying graph of directed or partially directed graph G is the graph resulted by removing all the designations ‘head’ and ‘tail’ from the graph G. The indegree of a vertex v in a digraph is the number of arcs directed to v and the outdegree of a vertex v is the number of arcs directed away from v. Each loop at v counts one towards indegree and one towards outdegree. Theorem: In a digraph, the sum of indegrees and outdegrees are both equal to the number of edges. Proof: Each directed edge contributes one to the indegree at ‘head’ and one to the outdegree at ‘tail’. Subgraph: Let G be a graph with vertex set V (G) and edge set E(G). A graph H with vertex set V (H) and edge set E(H) is said to be subgraph of G if V (H) ⊆ V (G) and E(H) ⊆ E(G) and each edge of H has same end vertices as in G. Every graph G is a subgraph of itself. The subgraph of G other than G is called a proper subgraph. If H2 is a subgraph of H1 and H1 is a subgraph of G then H2 is also a subgraph of G. A single vertex of a graph G is a subgraph of G. A single edge of a graph G is a subgraph of G. Induced subgraph: In a graph G the induced subgraph on a set of vertices H = h1, h2, . . . , hk denoted as G(H) has H as its vertex set and it contains every edge of G whose end vertices are in H i.e. V (G(H)) = H and E(G(H)) = {e ∈ E(G) / the end vertices of e are in H} In other words if subgraph H satisfies the added property that uv ∈ E(G(H)) if and only if uv ∈ E(G) then H is a induced subgraph of G. Spanning subgraph: A subgraph H of a graph G is a spanning subgraph if V (H) = V (G). For the graph G , H1 is a spanning subgraph but not an induced subgraph as there is an edge between 3 and 4 in G but it is not in H1. Where H2 is an induced subgraph but not a spanning subgraph. Walk: A walk of a graph G is a finite alternating sequence of vertices and edges. If W is a walk between the vertices v0 and vk then we denote it as v − vk. Here v0 and vk are called origin and terminus while remaining vertices are called internal vertices. The number of edges in the walk is called the length of the walk. Closed walk: A v − vk walk of a graph G is called closed if v0 = vk. 4