Practice Problems Graph Theory

Discrete Mathematics for Comp.
Science (CS F-222)

Practice Problems
Graph Theory
Q.1 Which sequence is not a possible degree sequence for simple graph?
(A) 0,0,1,2,1,1,1,0,0,. (B) 0,0,5,0,3,0,4,0,0, (C) 0,0,1,3,2,0,2,0,0,. (D) 0,1,2,1,3,1,4,0,0,.
Q.2 Which graph has an Euler circuit?
Q.3 Exactly which of the graphs shown below are not planar?
(A) G3,G6,G7 (B) G2,G3,G7 (C) G2,G3,G6 (D) G2,G3,G6,G7
Q.4 Let G be a simple, connected 4-regular planar graph. If G has 12 edges, how many faces are there in a
plane representation of G?
(A) 8 (B) 12 (C) 4 (D) 5
Q.5 Which of the following graphs are isomorphic?
(A) G1 & G2 Only (B) G1 & G3 Only (C) G2 & G3 (D) None of the above
Q.6 The following is claimed to be the set of nodal degrees of a graph G (Chartrand’s definition of graph)
with 5 vertices: 2,4,3,4,3.
(A) G does not exist because it is impossible to connect two nodes to four other vertices.
(B) G does not exist because this node set violates the theorem about the relationship between the sum
of the nodal degrees and the number of edges.
(C) There is a graph and it has 8 edges.
(D) There is a graph and it has 9 edges.
Q.7 For the graph in question above (ignore the edge weights):
(A) It is regular and bipartite. (B) Regular but not bipartite.
(C) Bipartite but not regular (D) Not bipartite and not regular
Q.8 Which of the following graphs can be drawn without edge crossings?
(A) The wheel graph on ten vertices. (B) The complete graph on six vertices
(C) The complete graph on five vertices (D) The utility graph.
Q.9 Which of the graphs has an Euler circuit?

(A) Graph 2 only (B) Graph 1 only (C) Graphs 1 and 3 (D) Graph 3 only
Q.10 Which of the graphs has an Euler path but no Euler circuits?
(A) Graph 3 only (B) Graphs 1 and 2 (C) Graph 2 only (D) Graph 1 only
Q.11 In a complete directed graph with 12 vertices the total number of Hamilton circuits that start at vertex A
is
(A) 11!. (B) 10!/2 (C) 12! (D) 13!
Q.12 Let G be a graph. Which of the following statements are equivalent to each other?
(i) G contains no odd-length cycles. (ii) G is bipartite.
(iii) G is 2-colorable. (iv) The maximum vertex degree of G is 1.
(A) (i), (ii) (B) (i), (ii), (iii) (C) (iii), (iv) (D) (ii), (iii), (iv)
Q.13 Suppose that a graph on 13 vertices has 12 edges and no cycles. How many connected components does
it have?
(A) 1 (B) 2 (C) 3 (D) 4
Q.14 Suppose I have a connected graph with 7 vertices, of degrees 1, 2, 4, 4, 6, 8, and 9. Does the graph have
an Euler path or Euler circuit?
(A) It has an Euler circuit
(B) It has an Euler path, but no Euler circuit
(C) It has neither an Euler path nor an Euler circuit
(D) Not enough information to tell
Q.15 Let’s change the question slightly. Suppose a connected graph has 4 vertices of degrees 3, 3, 3, and 3.
Does it have a Hamilton path or circuit?
(A) It has an Euler circuit
(B) It has an Euler path, but no Euler circuit
(C) It has neither an Euler path nor an Euler circuit
(D) Not enough information to tell
Q.16 Which of the properties listed below are true of a Hamilton cycle?
(I) It visits every vertex. (II) It follows every edge. (III) It visits every vertex only once.
(A) I, III (B) I, II, III (C) I, II (D) II, III
For the next three questions, consider the following data:

let S be a set of n elements {1, 2, ……………n} and G a graph with 2n vertices, each vertex corresponding to a
distinct subset of S. two vertices are adjacent if the symmetric difference of the corresponding sets has exactly 2
elements. Note: The symmetric difference of two set R1 and R2 is defined as (R1/R2) U (R2/R1).
Q.17 Whether every vertex in G has the same degree.

(A) Yes (B) no
(C) yes, for some value of n (D) some graph does not exists.
Q.18 What is the degree minimum degree of a vertex in G?
(A) n (B)0 (C)1 (D) n-1
Q.19 How many connected components does G have?
(A) 2 (B) 1 (C) n (D) n+2
Q.20 Km,n is the complete bipartite graph on m+n vertices. What is the largest k such that km;n is k-connected?
(A) min(m ; n) (B) max (m ; n). (C) m (D) n
Q.21 If a simple graph has 10 vertices and is connected, The no of edges can be:
(A) exactly 20 (B) 30 (C) between 10 and 30 (D) between 9 and 45
Q.22 What is the chromatic number of the graph?
(A) 3 (B) 4
(C) 5 (D) 6
Q.23 Find the largest maximal matching in each of the graph given below
(A) 3,3,4 (B) 3,3,3 (C) 3,4,4 (D) 4,4,4
Q.24 Select the correct statement

(A) No graph can have degree sequence 5,4,3,3,2,2,1.
(B) C5 is bipartite.
(C) The graphs W3 K4 are isomorphic
(D) There exists a full 3-ary tree with 16 vertices that has a path of length 6.
Q.25 An independent set I of nodes of a graph is a collection of nodes of the graph such that no two nodes of
I are adjacent. For the following sets, circle the maximal independent sets for the graph G.
(A) {A, C, F} (B) {A,C}
(C) {B, E,D} (D) {B, E,G, J}
Q.26 Find a maximum matching and a minimum vertex cover for the bipartite graph shown below
(A) maximum matching: {{a,1}, {b,3}, {c,4}}, minimum vertex cover:{a,b,4}.

(B) maximum matching: {{a,1}, {c,4}}, minimum vertex cover:{a,b,4}.
(C) maximum matching: {{a,1}, {b,3}, {c,4}}, minimum vertex cover:{a,c}.
(D) maximum matching: {{a,1}, {b,4}}, minimum vertex cover:{d,c,2}.
Q.27 Let KA,B with |A| = |B| = n a complete bipartite graph, that is such that it contains all possible edges
between elements of A and elements of B. How many perfect matching’s are there in G?
(A) n (B) n! (C) 2n (D) 2n!
Q.28 If a connected planar simple graph G has 6 vertices with degrees 2,2,2,3,3,4 then the number of regions
in a planar representation is:
(A) 4 (B) 5 (C) 6 (D) 7
Q.29 There are two complete disconnected components G1 and G2 of graph G. G1 has 21 and G2 has 28 edges.
How many edges are needed more to convert G in to an complete graph connected graph.
(A) 56 (B) 112 (C) 76 (D) 36
Q.30 K6,3 is a complete partite graph. How many edges are lacking to convert it in to complete graph having
same number of vertices as K6, 3 has.
(A) 18 (B) 34 (C) 28 (D) 39
Q.31 If we represent a complete bipartite graph Km, n using adjacency matrix representation. What is the
maximum numbers of zero entries in any row of adjacency matrix
(A) min (m, n) (B) max (m,n) (C) m (D) n
Q.32 If ∝ (G) is cardinality of largest matching then matching of graph G then which of the following options
represent the correct matching number corresponding to given graph.
∝ (Cn ) (P) ⌊𝑛/2⌋
∝ (Pn ) (Q) n
∝ (Kn ) (R) 2n
(A) i = P, ii=Q iii=R (B) i = Q, ii=P iii=R
(C) i = R, ii=Q iii=Q (D) i = P, ii=P iii=P
Q.33 Find the cardinality of largest matching to complete partite graph Km, n
(A) min(m, n) (B) max (m, n) (C) m+n-1 (D) m-n
Q.34 If G is graph of n vertices then what is cardinality of a perfect matching of G, if every vertex of G is
matched
(A) n/2 (B) n (C) n-1 (D) 2n-1

Practice Problems Graph Theory

Uploaded by

Copyright:

Available Formats

Practice Problems Graph Theory

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Practice Problems Graph Theory

Uploaded by

Copyright:

Available Formats

Which sequence is not a possible degree sequence for simple graph?

Which graph has an Euler circuit?

Discrete Mathematics for Comp.

Science (CS F-222)

Q.2 Which graph has an Euler circuit?

(A) G3,G6,G7 (B) G2,G3,G7 (C) G2,G3,G6 (D) G2,G3,G6,G7

Q.5 Which of the following graphs are isomorphic?

Q.9 Which of the graphs has an Euler circuit?

For the next three questions, consider the following data:

Q.17 Whether every vertex in G has the same degree.

(A) 3,3,4 (B) 3,3,3 (C) 3,4,4 (D) 4,4,4

Q.24 Select the correct statement

(A) {A, C, F} (B) {A,C}

(C) {B, E,D} (D) {B, E,G, J}

(A) maximum matching: {{a,1}, {b,3}, {c,4}}, minimum vertex cover:{a,b,4}.

You might also like