Question Bank Subject: - Graph Theory(ECS-

505)Branch: - Computer ScienceYear: - 3

rd
Subject Teacher: - Ms. Payal Kansal
Unit: - 1
Year (2003-2004)1)
Prove that the sum of the degrees of the vertices of a graph is equal to twice thenumber of edges. Does the
theorem hold for a multigraph? Justify your answer withexample?
2)
For the following pair of graphs, determine whether or not the graphs areisomorphic? Give the
justification for your answer?
3)
Proof that a simple graph with n vertices and k components can have at most (n-k)(n-k+1)/2 edges?
4)
Prove that the finite connected graph is Eulerian if and only if each vertex has evendegree?
5)
Prove that, in a complete graph with n vertices, there are (n-1)/2 edge disjoint Hamiltonian circuits, if n is
odd number >= 3?
6)
Define the following with one example each :a)Subgraph b)Spanning Subgraphc)Homeomorphic
graphsd)Unicursal linee)Arbitrarily traceable graph
Year (2004-2005)
1)Prove that in a graph the number of the vertices with odd degree is even?2)Find a path of length 9 and a
circuit of length 8 in the Peterson graph?3)Find three Hamiltonian circuits in dodecahedron?4)Prove that
every graph with n vertices with at least n edges contains a circuit?5) Write a brief note of 200 words or
more on the travelling sales person?
Year (2005-2006)
1)Prove that the sum of the degrees of all vertices of a graph is even?2)Prove that a simple graph with n
vertices and k components can have at most (n-k)(n-k+1)/2 edges?3)Define an Euler graph? Find an
example of eulerian graph which is notHamiltonian?4)Define the ring sum of two graphs? Find the ring
sum of the following graphs G1,G2?
01:1303:41

5)Define the Hamiltonian path? Find an example of a non Hamiltonian graph with aHamiltonian path?
6)Prove that a graph is an Euler graph if and only if it can be decomposed intocircuits?
7)Prove that in a complete graph with n vertices there are (n-1)/2 edge disjointHamiltonian circuits and n
>= 3?
8)Describe briefly the travelling Salesman problem?9)Define isomorphism between two graphs? Verify
whether the following graphs areisomorphic to each other?
Year (2006-2007)
1) Define a bipartite graph? Show that the complement of a bipartite graph need not to be a bipartite?
2)Discuss the Konigsberg Bridge problem?
3)Define the following with one example each :a)Infinite graph b)Hamiltonian pathc)Component of
a graphd)Euler graphe)Spanning subgraph
4)Define isomorphic graph? Draw three isomorphic graph of the following graph?
5)Differentiate, with example, a simple graph and a multigraph. Show that themaximum number of edges
in a simple graph with n vertices n (n-1)/2?
6)What is the largest number of vertices in a graph witha)35 edges if all vertices are of degree
at least 3. b)24 edges and all vertices of the same degree.
Year (2007-2008)
1)Define the degree of a vertex in a graph. Prove that the number of vertices of odddegree in a graph is
always even?
2)Prove that in graph with n vertices and k components the maximum number of edgescannot exceed (n-
k)(n-k+1)/2?
3)Define an Eulerian and a Hamiltonian graph? Give examples of Eulerian nonHamiltonian graph G, and
Hamiltonian non-eulerian graph G2 with number ofvertices >= 10?
4)Define connected graph? Prove that for a graph with exactly two vertices of odddegree, there must be a
path joining these two vertices?
5)Draw a graph G with Hamiltonian path without Hamiltonian circuit with number ofvertices >= 20?

ADDownload to read ad-free.

Year (2009-2010)
1)Define the degree of a vertex in a graph? Prove that the sum of the degrees of allvertices of a graph in a
graph is twice the number of edges in graph?
2)Define isomorphism of graphs? For the following pair of graphs , determine whetheror not the graphs
are isomorphic. Explain your answer?
3)Prove that a simple graph with n vertices and k components can have atmost (n-k) (n-k+1) edges?
4)Discuss travelling sales man problem?5)Define the following with one example.a)Complete
graph b)Eulerian graphc)Hamiltonian graphd)Bi-partite graphe)Cut points of a graph
Unit: - 2
Year (2003-2004)
1)If G is tree with n vertices then prove that it has exactly n-1 edges?
2)Explain what is meant by spanning tree? Find four spanning trees for the followinggraph :
3)Find the shortest path from a to z of the following graph using Dijkstra Algorithm :
4)Use the algorithm of Kruskal to find a minimum weight spanning tree in thefollowing graph ---
5)Prove that a connected graph G is a tree if G has fewer edges than vertices?6)Take any spanning tree in
the following graph. List all the seven fundamental cut-sets with respect to this tree---

ADDownload to read ad-free.

Year (2004-2005)
1)Define the pendent vertices in a binary tree? Prove that the number of the pendentvertices in a binary
tree with n vertices is (n+1)/2?
2)Define a spanning tree of a graph? Find three spanning tree in the Peterson graph?
3)Write an algorithm to find the shortest spanning tree in a weighted graph?
4)Define the shortest path in a weighted graph? Describe the Dijkstra algorithm to findthe shortest path m
a weighted graph with vertices more than 7?
5)Define the cut set of a graph? Find five cut sets of the following graph?
Year (2005-2006)
1)Define the centre of a tree? Prove that every tree has one or two centre?
2)Prove that if in a graph G there is one and only one path between every pair ofvertices is tree?
3)Define a spanning tree in a graph? Find four spanning trees In the dodecahedrongraph?
4)State the two algorithms to find the shortest spanning tree in a weighted graph. Writethe details of one
of these algorithms?
Year (2006-2007)
1)
Apply prime’s algorithm to find a minimal spanning tree of the following graph?
2)
Find shortest path from v1 to v8 using Dijkstra algorithm in the following graph.
3)
Define spanning tree of a graph? Show that a Hamiltonian path in a graph is aspanning tree?
4)
Show a tree in which its diameter is not equal to twice of the radius? Under whatcondition does this
inequality hold? Elaborate?
5)
What are the different properties when a graph G with n vertices is called a tree?

ADDownload to read ad-free.

Year (2007-2008)1)
Prove that every tree has one or two centres?
2)
Define a spanning tree of a graph? Find four spanning trees of the followingPeterson’s graph?
3)
Prove that w.r.t any of its spanning trees a connected graph with n vertices and eedges has (n-1) tree
branches and (e-n+1) chords?
4)
Find a shortest spanning tree in a weighted graph G, using the PRIM’s algorithmswhere G is as follows?
5)
Construct a tree with 16 vertices, each corresponding to a spanning tree of a labeledcompleted graph with
four vertices?
6)
Define fundamental circuit and cut-sets. Find five fundamental circuits andfundamental cut-sets of the
graph---
Year (2009-2010)
1)If G is a non-trivial tree, then prove that G contains at least two vertices of degree 1?
2)Define binary trees and discuss two important applications of it?
3)Apply Dijakstra algorithm to find out the shortest path from the vertices a to z in thefollowing graph?
4)Use prims algorithm to find out the minimal spanning tree of the following graph?
5)Define fundamental circuits? Find the sets of fundamental circuits(four only) of thegraph given above?
Take any spanning tree and find it corresponding to thatspanning tree?
6)Define eccentricity of the vertex and centre of a graph? Find the centre of the graphgiven above?

ADDownload to read ad-free.

Unit: - 3
Year (2003-2004)
1)Draw a graph withEdge connectivity = 4Vertex connectivity = 3Degree of every vertex >= 5
2)Show that the complete bipartite graph K3,3 is non-planer?
3)In a simple connected planner graph G, there are r regions, v vertices (v>= 3) and eedges (e>1) then
a)e >= 3*2^r
b)e <= 3v – 6c)there is a vertex v of G such that degree(v) <= 5
4)Prove that a graph has a dual if and only if it is planar?5)Show by sketching that the thickness of nine
vertex complete graph is three?
Year (2004-2005)
1)Define a planar graph? Prove that for a connected planar with n vertices and e edgese <= 3n - 6 and e
<= 2n – 4?
2)Write an algorithm to detect the planarity of a graph? Detect the planarity of thegraph k5 and K3,3?
3)Define the dual of the graph? Show that the complete graph of four vertices is selfdual? Also, if n, e and
f are the number of vertices, number of edges and number of regions of a planar graph, find these
numbers for the dual of this graph?
Year (2005-2006)
1)Prove that in a graph every circuit has an even number of edges in common with anycut set?2)Define a
planar graph? State and prove the Euler’s theorem for a planar graph?
Year (2006-2007)
1)Define the edge connectivity and vertex connectivity of a connected graph? Findthem for the following
graphs—
2)Show that a complete graph k n is planar if n <= 4?
3)Draw a spanning tree of the following graph given below and list all the fundamentalcircuits with
respect to this tree---
4)Find the dual of the following graph?

ADDownload to read ad-free.

5)Prove that a graph G has a dual if and only if it is a planar?

6)Show by sketching that the thickness of eight-vertex complete graph is two?
Year (2007-2008)
1)Define the vertex connectivity and edge connectivity of a graph? Prove that for agraph G with n
vertices and e edges vertex connectivity <= edge connectivity <=2e/n?2)Define the capacity of a cut-set?
Prove that the maximum flow possible between twovertices a and b in a network is equal to the minimum
of capacities of all cut-setswith respect to a and b?3)Define a separable graph? Prove that in a non-
separable graph G set of edgesincident on each vertex of G is a cut-set?4)Define a planar graph? Prove
that a complete graph with five vertices is non-planar?5)For a planar graph with n vertices and e edges
prove that e <= 3n-6?6)Define thickness and crossing number of a graph? Find thickness and
crossingnumbers of the graph k5 and K3, 3?
Year (2009-2010)
1)Define a planar graph? State and prove the euler’s formula for planar graph?2)Define edge and vertex
connectivity of a graph? Prove that the vertex connectivity of any graph will never be more than the edge
connectivity?3)Show that the kuratowski’s first (K5) and second (K3,3) are nonplanar graphs?4)Show
that a graph has a dual if and only if it is planar?5)Define the thickness of a graph, give one example?
Find the thickness ofKuratowski’s first and second graph?6)Define cut-sets? List all cut-sets with respect
to the vertex pair v2, v3 in thefollowing graph?
Unit: - 4
Year (2003-2004)
1)What is the difference between incidence and adjacency matrices? Prepare bothmatrices for given
graph---2)Define the term with example— a)Circuit matrix b)Cutset matrixc)Fundamental cut set matrix

ADDownload to read ad-free.

3)Prove that m-vertex graph is a tree if its chromatic polynomial is Pm (n) = n (n-1) ^(m-1)?
4)Define Arborescence with example? Discuss its one application? Also prove that anArborescence is a
tree in which every vertex other than root has an in-degree ofexactly one?
Year (2004-2005)
1)Define a vector space associated with a graph G and its two subspaces the circuitsubspace and cut set
subspace? Find all the distinct bases of the circuit subspace ofK5?2)Define the circuit matrix B (G) of a
connected graph G with n vertices and e edges?Prove that the rank of B (G) is e-n+1?3)Define the
adjacency matrix A (G) of a simple graph G? Prove that two graphs G1and G2 are isomorphic if and only
if A (G1) and A (G2) differ only by the permutations of rows and columns?4)Define a k-chromatic graph?
Prove that every tree with two or more vertices is 2-chromatic? Find an example of a 2-chromatic graph
which is not a tree. Also, findthe chromatic polynomial of a tree with n vertices?
Year (2005-2006)
1)Define a vector space for a graph G, and the circuit subspace and cut sets subspaceof this vector space?
Prove that the circuit subspace and cut set subspace areorthogonal to each other?2)Define the incidence
matrix, of a graph G? Prove that the rank of an incidencematrix of a connected graph with n vertices is n-
1?3)Define the circuit matrix B of a connected graph with n vertices and e edges? Provethat the rank of B
is e-n+1?4)Define the chromatic number and chromatic polynomial of a graph? Find thechromatic
number and the chromatic polynomial of the following graph-----
Year (2006-2007)
1)Define basis vectors of a graph? Find the number of distinct basis possible in a cut-set subspace?
2)Definea)Reduced incidence matrix b)Fundamental circuit matrix andc)Fundamental cut-set matrixOf a
connected graph? Also device the relationship between them?3)Consider the circuit matrix (B) and
incidence matrix (A) of a simple connectedgraph whose columns are arranged using the same order of
edges. Then prove thatevery row of B is orthogonal to every row of A? also verify the result for
thefollowing graph-----

ADDownload to read ad-free.

4)What do you mean by chromatic number and chromatic polynomial of a graph?Determine the
chromatic number and chromatic polynomial of the followinggraphs---
Year (2007-2008)
1)Define a vector space of a graph? Find five base and number of vectors in the vectorspace of graph
given below? Also find five cut-set vectors and five circuit vectors ofthis vector space?2)Define the
adjacency matrix of a graph? Find the rank of the regular graph with nvertices and with degree p (<n) of
any vertex?3)Define reduced matrix AF, fundamental circuit matrix bf and the fundamental cut-setmatrix
Cf of a connected graph G with n vertices and e edges. Derive therelationship among AF, bf and Cf?
4)Define the chromatic polynomial of a graph? Find the chromatic polynomial of thegraph given below?
5)State and prove five colour theorem?
Year (2009-2010)
1)Define basis vectors of a graph? Show that the number of distinct basis possible in acut-set subspace
is :1/r! (2^r – 2^0) (2^r – 2^1) (2^r – 2^2)……. (2^r – 2^ r-1)2)If B is a circuit matrix of a connected
graph G, with e edges and n vertices, thenshow that the rank of B is equal to the nullity of G?3)Prove that
the rank of a cut-set matrix is equal to the rank of the graph?4)Prove that the m-vertex graph is a tree if
and only if its chromatic polynomial isPm(x) = x (x-1) ^m-1