Graphtheory
Question 1 
What is the maximum number of edges in an acyclic undirected graph with n vertices?
n  1  
n  
n + 1  
2n  1 
= n  1
Question 2 
What is the number of vertices in an undirected connected graph with 27 edges, 6 vertices of degree 2, 3 vertices of degree 4 and remaining of degree 3?
10  
11  
18  
19 
By Handshaking Lemma,
6 * 2 + 3 * 4 + (x  9) * 3 = 27 * 2
24 + (x  9) * 3 = 54
x = 19
Question 3 
Graph G is obtained by adding vertex s to K_{3,4} and making s adjacent to every vertex of K_{3,4}. The minimum number of colours required to edgecolour G is _____.
7 
The vertex in the set of size 3 has 4 edges connected to 4 vertices on other set. So, edge color of G is max(3,4) i.e. 4.
When a vertex is added to the graph with 7 vertices ( K_{3x4} has 7 vertices), there would be 7 edges associated to that new vertex. As per the edge coloring “no two adjacent edges have same color).
As the new vertex with 7 edges need to be colored with 7 colors, the edge color of graph G is 7.
Question 4 
36 
Given 10 vertices,
Then we can have a complete graph with 9 vertices and one isolated verted.
Number of edges in complete graph with 9 edges is n(n1)/2 = 9*8/2 = 36
Question 5 
A ^3  
A^ 3 divided by 2  
A ^3 divided by 3  
A ^3 divided by 6 
Question 6 
Which of the following statements is/are TRUE?
The chromatic number of the graph is 3.  
The graph has a Hamiltonian path  
The following graph is isomorphic to the Peterson graph.  
The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.) 
Peterson graph ihas hamiltonian path but not hamiltonian cycle
Given graph in option C is isomorphic as the given has same number of vertice, edges, degree sequence and cycles.
LArgest independent set can be more than 3
Question 7 
The diagonal entries of A 2 are the degrees of the vertices of the graph.  
If the graph is connected, then none of the entries of A^ n + 1 + I n can be zero.  
If the sum of all the elements of A is at most 2( n 1), then the graph must be acyclic.  
If there is at least a 1 in each of A ’s rows and columns, then the graph must be Connected. 
The entries aii show the number of 2length paths between the nodes i and j. Why this happens is easy to see: if there is an edge ij and an edge jk, then there will be a path ik through j. The entries ii are the degrees of the nodes i.
Similarly in A^3 we have the entries aii that show the number of 3length paths between the nodes i and j.
In A^n1 + I n, we will have at least n1 length paths, so there is no possibility of zero entires
Question 8 
Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent if i  j = 8 or i  j = 12. The number of connected components in G is
8  
4  
12  
25 
1 — 9 — 17 — ......... — 97
2 — 10 — 18 — ......... — 98
3 — 11 — 19 — ......... — 99
4 — 12 — 20 — ......... — 100
5 — 13 — 21 — ......... — 93
6 — 14 — 22 — ......... — 94
7 — 15 — 23 — ......... — 95
8 — 16 — 24 — ......... — 96
We have covered all vertices using 8 vertex sets considering only i  j = 8. Using i  j = 12 we can see the vertex 1 is connected to 13, 2 to 14, 3 to 15 and 4 to 16. So the top 4 vertex sets are infact connected to the bottom 4 sets, thus reducing the connected components to 4.
Question 9 
(a) Prove by induction that the expression for the number of diagonals in a polygon of n sides is n(n3)/2.
(b) Let R be a binary relation on A = {a, b, c, d, e, f, g, h} represented by following two component digraph. Find the smallest integers m and n such that mm = R^{n}.
Theory Explanation. 
Question 10 
Let (A, *) be a semi group. Furthermore, for every a and b in A, if a ≠ b, then a*b ≠ b*a.
(a) Show that for every a in A
a*a = a
(b) Show that for every a, b in A
a*b*a = a
(c) Show that for every a, b, c in A
a*b*c = a*c
Theory Explanation. 
Question 11 
Let G be a connected, undirected graph. A cut in G is a set of edges whose removal results in 0 being broken into two or more components which are not connected with each other. The size of a cut is called its cardinality. A mencut of G is a cut in G of minimum cardinality. Consider the following graph.
(a) Which of the following sets of edges is a cut?
(i) {(A,B), (E,F), (B,D), (A,E), (A,D)}
(ii) {(B,D), (C,F), (A,B)}
(b) What is the cardinality of a mincut in the graph?
(c) Prove that if a connected undirected graph G with n vertices has a mincut of cardinality K, then G has atleast (nk/2) edges.
Theory Explanation. 
Question 12 
Let S be a set of n elements {1, 2, …., n} and G a graph with 2^{n} vertices, each vertex corresponding to a distinct subset of S. Two vertices are adjacent iff the symmetric difference of the corresponding sets has exactly 2 elements. Note: The symmetric difference of two sets R^{1} and R^{2} is defined as (R^{1}/R^{2})∪(R^{2}/R^{1})
(a) Every vertex in G has the same degree. What is the degree of a vertex in G?
(b) How many connected components does G have?
Theory Explanation is given below. 
Question 13 
The minimum number of colours required to colour the vertices of a cycle with η nodes in such a way that no two adjacent nodes have the same colour is
2  
3  
4  
n  2[n/2] + 2 
Question 14 
Maximum number of edges in a nnode undirected graph without self loops is
n^{2}  
n(n1)/2  
n1  
(n+1)(n)/2 
Question 15 
Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between
k and n  
k – 1 and k + 1  
k – 1 and n – 1  
k + 1 and n – k 
If a vertex is removed then it results that all the components are also be disconnected. So removal can create (n1) components.
Question 16 
How many perfect matching are there in a complete graph of 6 vertices ?
15  
24  
30  
60 
(2n)!/n!×2^{n}
Given, 2n = 6 ⇒ n = 3
So, finally, 6!/3!×2^{3} = 15
Question 17 
A graph G = (V,E) satisfies E≤ 3V6. The mindegree of G is defined as . Therefore, mindegree of G cannot be
3  
4  
5  
6 
E ≤ 3v  6
Based on handshaking lemma, the minimum degree is (min×v)/2
⇒ (min×v)/2 ≤ 3v  6
Checking the options lets take min=6
(6×v)/2 ≤ 3v  6
0 ≤ 6 (Not satisfied)
And which is inconsistent.
Question 18 
The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same colour, is
2  
3  
4  
5 
→ a, b, c, d = 4
→ The minimum no. of colours required to colour a graph = 4 (no two adjacent vertices have same colours)
Question 19 
How many graphs on n labeled vertices exist which have at least (n^{2}  3n)/2 edges?
Maximum no. of vertices = n(n1)/2 = v
No. of graphs with minimum b edges is
= C(v,e) + C(v,e+1) + C(v,e+2) + ... + C(v,v)
= C((v,ve) + C(v,v(e+1)) + C(v,v(e+2)) + ... + C(v,0)
= C(a,n) + C(a,n1) + C(a,n2) + ... + C(a,0) (since ab=n)
= C(n(n1)/2,n) + C(n(n1)/2,n1) + ... + C(n(n1)/2,0)
Question 20 
Let G_{1} = (V,E_{1}) and G_{2} = (V,E_{2}) be connected graphs on the same vertex set V with more than two vertices. If G_{1} ∩ G_{2} = (V, E_{1} ∩ E_{2}) is not a connected graph, then the graph G_{1} U G_{2} = (V, E_{1} U E_{2})
cannot have a cut vertex
 
must have a cycle  
must have a cutedge (bridge)
 
has chromatic number strictly greater than those of G_{1} and G_{2}

(A)
False, since in G_{1}∪G_{2} 'C' is a cut vertex.
(B) True, for all conditions.
(C)
False. G_{1}∪G_{2} has no bridge.
D)
False. G_{1}∪G_{2}, G_{1}, G_{2} all the three graphs have chromatic number of 2.
Question 21 
Let G be a simple connected planar graph with 13 vertices and 19 edges. Then, the number of faces in the planar embedding of the graph is:
6  
8  
9  
13 
F = E  V + 2 [From Euler's formula i.e., F + V  E = 2]
F = 19  13 +2
F = 8
Question 22 
Let G be a simple graph with 20 vertices and 100 edges. The size of the minimum vertex cover of G is 8. Then, the size of the maximum independent set of G is
12  
8  
Less than 8  
More than 12

Edges = 100
Minimum cover of vertex G is = 8
Maximum Independent set of G = No. of vertices  Minimum cover of vertex G
= 20  8
= 12
Question 23 
Which one of the following graphs is NOT planar?
G_{1}  
G_{2}  
G_{3}  
G_{4} 
which is planar
G_{3} can also be drawn as
which is planar
G_{4} can also be drawn as
which is planar
But G_{1} cannot be drawn as planar graph.
Hence, option (A) is the answer.
Question 24 
The 2^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of vertices of degree zero in G is:
1  
n  
n+1  
2^{n} 
= no. of subsets with size less than or equal to 1
= n+1, because in question it is given that the two vertices are connected if and only if the corresponding sets intersect in exactly two elements.
Question 25 
The 2^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The maximum degree of a vertex in G is:
2^{n2}  
2^{n3} × 3  
2^{n1} 
(k(_{c}))_{2} 2^{nk}
∴ We need to find 'k' value such that, the value will be maximum.[k should be an integer].
If you differentiate (k(_{c}))_{2} 2^{nk} w.r.t. k and equal to 0.
You will get k = 2/(log_{e})2 which is not an integer.
So you can see it like
∴ The maximum degree 3⋅2^{n3} at k=3 or k=4.
Question 26 
The 2^{n} vertices of a graph G corresponds to all subsets of a set of size n, for n ≥ 6. Two vertices of G are adjacent if and only if the corresponding sets intersect in exactly two elements.
The number of connected components in G is:
n  
n+2  
2^{n/2}  
2^{n} / n 
While other nodes are connected so that total number of connected components is (n+1)+1
(here we are adding 1 because it is connected corresponding remaining vertices)
= n+2
Question 27 
The minimum number of edges in a connected cyclic graph on n vertices is:
n  1  
n  
n + 1  
None of the above 
In cyclic graph:
No. of edges = No. of vertices
⇒ n = n
Question 28 
Prove that in finite graph, the number of vertices of odd degree is always even.
Theory Explanation. 
Question 29 
The number of distinct simple graphs with upto three nodes is
15  
10  
7  
9 
Question 30 
The number of edges in a regular graph of degree d and n vertices is _________.
d*n/2 
d * n = 2 * E
∴ E = d*n/2
Question 31 
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?
There exists a cutset in G having all edges of maximum weight  
There exists a cycle in G having all edges of maximum weight  
Edge e cannot be contained in a cycle  
All edges in G have the same weight 
(B) False, because the cutset of heaviest edge may contain only one edge.
(C) False. The cutset may form cycle with other edge.
(D) False. Not always true.
Question 32 
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is
4  
7  
23  
99 
j = i +1
(or)
j = 3i
Second option will help us reach from 1 to 100 rapidly. The trick to solve this question is to think in reverse way. Instead of finding a path from 1 to 100, try to find a path from 100 to 1.
So, the edge sequence with minimum number of edges is
1 → 3 → 9 → 10 → 11 → 33 → 99 → 100
which consists of 7 edges.
Question 33 
11 
v  e + f = 2
v is number of vertices
e is number of edges
f is number of faces including bounded and unbounded
8e+5=2
=> 132 =e
The number of edges are =11
Question 34 
Let M be the adjacency matrix of G.
Define graph G2on the same set of vertices with adjacency matrix N, where
Which one of the following statements is true?
Question 35 
What is the chromatic number of the following graph?
2  
3  
4  
5 
→ Chromatic number of a graph is the smallest number of colours needed to colour the vertices so that no two adjacent vertices share the same colour.
Question 36 
What is the size of the smallest MIS(Maximal Independent Set) of a chain of nine nodes?
5  
4  
3  
2 
(2, 5, 8) is the maximal independent set for a chain of 9 nodes. If we add any start node to the set then it will not be MIS.
Independent set:
A set of vertices is called independent set such that no two vertices in the set are adjacent.
Question 37 
G is a simple undirected graph. Some vertices of G are of odd degree. Add a node v to G and make it adjacent to each odd degree vertex of G. The resultant graph is sure to be
Regular  
Complete  
Hamiltonian  
Euler 
→ In Euler graph all degrees must be even for all nodes. And number of odd degree vertices should be even.
→ So, degree of this new node will be even and as a new edge is formed between this new node and all other nodes of odd degree hence here is not a single node exists with degree odd so this is Euler graph.
Question 38 
Consider the undirected graph G defined as follows. The vertices of G are bit strings of length n. We have an edge between vertex u and vertex v if and only if u and v differ in exactly one bit position (in other words, v can be obtained from u by flipping a single bit). The ratio of the chromatic number of G to the diameter of G is
1/(2^{n1})  
1/n  
2/n  
3/n 
That will give us a bipartite graph, with chromatic number = 2
Also from the same we can conclude that we need for a 'n' bit string, to traverse no more than (n1) edges or 'n' vertices to get a path between two arbitrary points. So the ratio is (2/n).
Question 39 
Which of the following graphs is/are planner?
Theory Explanation is given below. 
→ Let us assume K_{33}is a planar graph. Then it satisfy the useful corollary. As there is no triangle in K_{33}.
Let G be a connected planar graph with n vertices and m edges, and no triangles. Then m≤2n4.
Where m=9, n=6
⇒ 9 ≤ 12  4
⇒ 9 ≤ 8, which is to be false, then K_{33} is nonplanar graph.
(ii) G_{2} is a planar graph. Because it can be redrawn like as below.
(iii) Let us assume G_{3} be a planar graph then it also be satisfy useful corollary.
Where m=9, n=6
then 9 ≤ 124
9 ≤ 8 is False
So, G_{3} is nonplanar graph.
Answer: Only G_{2} is planar graph.
Question 40 
Choose the correct alternatives (More than one may be correct).
A graph is planar if and only if,It does not contain subgraphs homeomorphic to k_{5} and k_{3,3}.  
It does not contain subgraphs isomorphic to k_{5} or k_{3,3}.  
It does not contain a subgraph isomorphic to k_{5} or k_{3,3}.  
It does not contain a subgraph homeomorphic to k_{5} or k_{3,3}. 
Question 41 
The maximum number of possible edges in an undirected graph with a vertices and k components is ________.
(nk)(nk+1)/2 
To get maximum, take one vertex each for each component, except last component.
Now, k1 components have 1 vertex each and so on edges.
The last component has (n(k1)) vertices. So make the last component complete, i.e., it has ^{n(n1)}C_{2}
= (nk)(nk+1)/2
= maximum no. of edges
Question 42 
Maximum number of edges in a planar graph with n vertices is ________
3n  6 
⇒ (3n  2) = 3n  6
Question 43 
A nonplanar graph with minimum number of vertices has
9 edges, 6 vertices  
6 edges, 4 vertices  
10 edges, 5 vertices  
9 edges, 5 vertices 
The above graph with 5 vertices and 10 edges is nonplanar.
Question 44 
Let T be a Depth First Tree of a undirected graph G. An array P indexed by vertices of G is given. P[V] is the parent of vertex V, in T. Parent of the root is the root itself.
Give a method for finding and printing the cycle formed if the edge (u,v) of G not in T (i.e., e ∈ G − T) is now added to T.
Time taken by your method must be proportional to the length of the cycle.
Describe the algorithm in a PASCAL – like language. Assume that the variables have been suitably declared.
Theory Explanation. 
Question 45 
(a) If G is a group of even order, then show that there exists an element a ≠ e, the identity in g, such that a^{2} = e
(b) Consider the set of integers {1,2,3, 4,6,8,12,24} together with the two binary operations LCM (lowest common multiple) and GCD (greatest common divisor). Which of the following algebraic structures does this represent?
(i) group (ii) ring (iii) field (iv) lattice
Theory Explanation. 
Question 46 
Let G be the nonplanar graph with the minimum possible number of edges. Then G has
9 edges and 5 vertices  
9 edges and 6 vertices  
10 edges and 5 vertices  
10 edges and 6 vertices 
if n ≥ 3 then e ≤ 3n6 (for planarity)
where n = no. of vertices
e = no. of edges
Now lets check the options.
A) e=9, n=5
9 ≤ 3(5)  6
9 ≤ 15  6
9 ≤ 9
Yes, it is planar.
B) e=9, n=6
9 ≤ 3(6)  6
9 ≤ 18  6 9 ≤ 12 Yes, it is planar.
iii) e=10, n=5
10 ≤ 3(5)  6
10 ≤ 15  6
10 ≤ 9 No, it is not planar.
So, option C is nonplanar graph.
iv) e=10, n=6
10 ≤ 3(6)  6
10 ≤ 18  6
10 ≤ 12
Yes, it is planar.
Question 47 
Which of the following graphs has an Eulerian circuit?
Any kregular graph where k is an even number.  
A complete graph on 90 vertices.  
The complement of a cycle on 25 vertices.
 
None of the above. 
→ all vertices in the graph have an "even degree".
→ And the graph must be corrected.
Now in option (C) it is saying that the complement of a cycle on 25 vertices without complement the degree of each vertex is 2.
Now since there are 25 vertices, so maximum degree of each vertex will be 24 and so in complement of cycle each vertex degree will be 24  2 = 22.
There is a theorem which says "G be a graph with n vertices and if every vertex has a degree of atleast n1/2 then G is connected."
So we can say that complement of cycle with 25 vertices fulfills both the conditions, and hence is Eulerian circuit.
Question 48 
Which of the following statements is true for every planar graph on n vertices?
The graph is connected  
The graph is Eulerian
 
The graph has a vertexcover of size at most 3n/4  
The graph has an independent set of size at least n/3

(A) Consider the following disconnected graph which is planar.
So false.
(B) A graph is Eulerian if all vertices have even degree but a planar graph can have vertices with odd degree.
So false.
(D) Consider K_{4} graph. It has independent set size 1 which is less than 4/3.
So false.
Hence, option (C) is correct.
Question 49 
In a connected graph, a bridge is an edge whose removal disconnects a graph. Which one of the following statements is true?
A tree has no bridges  
A bridge cannot be part of a simple cycle  
Every edge of a clique with size 3 is a bridge (A clique is any complete sub graph of a graph)  
A graph with bridges cannot have a cycle 
∴ (A) is false
Since, every edge in a complete graph kn(n≥3) is not a bridge ⇒
(C) is false
Let us consider the following graph G:
This graph has a bridge i.e., edge ‘e’ and a cycle of length ‘3’
∴ (D) is false
Since, in a cycle every edge is not a bridge
∴ (B) is true
Question 50 
A graph is selfcomplementary if it is isomorphic to its complement for all selfcomplementary graphs on n vertices, n is
A multiple of 4  
Even  
Odd  
Congruent to 0 mod 4, or, 1 mod 4

Question 51 
The minimum number of colours that is sufﬁcient to vertexcolour any planar graph is ________.
4  
5  
6  
7 
Here it is asked about the sufficient number of colors, so with the worst case of 4 colors we can color any planar graph.
Question 52 
G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ___________.
16  
17  
18  
19 
Degree of each vertex ≥ 3
v = 2E
The relation between max and min degree of graph are
m ≤ 2E / v ≤ M
Given minimum degree = 3
So, 3 ≤2 E / v
3v ≤ 2E
3(n) ≤ 2(25)
n ≤ 50/3
n ≤ 16.6
(n = 16)
Question 53 
How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v_{1}, v_{2}, ...,v_{n}} of n vertices?
n(n1)/2  
2^{n}  
n!  
2^{n(n1)/2} 
Each subset of these edges will be form a graph.
No. of possible undirected graphs is 2^{(n C 2) ⇒ 2(n(n1)/2)}
Question 54 
Let G be an undirected complete graph on n vertices, where n > 2. Then, the number of different Hamiltonian cycles in G is equal to
n!  
1  
(n1)!  
The total number of hamiltonian cycles in a complete graph are
(n1)!/2, where n is number of vertices.
Question 55 
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is _______________.
24  
25  
26  
27 
V + R = E + 2 (1) where V, E, R are respectively number of vertices, edges and faces (regions)
Given V = 10 (2) and number of edges on each face is three
∴3R = 2E ⇒ R = 2/3E (3)
Substituting (2), (3) in (1), we get
10 + 2/3E = E + 2 ⇒ E/3 = 8 ⇒ E = 24
Question 56 
color(v_{i}) ← min{j ε N : no neighbour of vi is colored j}
Which of the following statements is/are TRUE?
This procedure results in a proper vertex coloring of G.  
The number of colors used is at most Δ(G) + 1.  
The number of colors used is at most Δ(G).  
The number of colors used is equal to the chromatic number of G. 
Question 57 
Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?
G_{1}=(V,E_{1}) where E_{1}={(u,v)(u,v)∉E}  
G_{2}=(V,E_{2} )where E_{2}={(u,v)│(u,v)∈E}  
G_{3}=(V,E_{3}) where E_{3}={(u,v)there is a path of length≤2 from u to v in E}  
G_{4}=(V_{4},E) where V_{4} is the set of vertices in G which are not isolated 
→ It strongly connected.
(A) G_{1}=(V,E_{1}) where E_{1}={(u,v)(u,v)∉E}
If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.
(B) G_{2}=(V,E_{2} )where E_{2}={(u,v)│(u,v)∈E}
Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.
Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.
(C) G_{3}=(V,E_{3}) where E_{3}={(u,v)there is a path of length≤2 from u to v in E}
This can also be true.
eg:
Both from each vertex to other vertex is also exists. So it is also strongly connected graph.
(D) G_{4}=(V_{4},E) where V_{4} is the set of vertices in G which are not isolated.
If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component
then no. of SCC = x + 1
G_{4} contain only ‘1’ component, which is not same as G.
Question 58 
Consider an undirected graph where selfloops are not allowed. The vertex set of G is {(i,j): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if a  c ≤ 1 and b  d ≤ 1. The number of edges in this graph is __________.
506  
507  
508  
509 
If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8.
From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.
⇒ (4*3) + (40*5) + (100*8) = 2*E
⇒ 1012 = 2*E
⇒ E = 506
Question 59 
An ordered tuple (d_{1}, d_{2}, ..., d_{n}) with d_{1} ≥ d_{2} ≥ ... d_{n} is called graphic if there exists a simple undirected graph with n vertices having degrees d_{1}, d_{2}, ..., d_{n} respectively. Which of the following 6tuples is NOT graphic?
(1, 1, 1, 1, 1, 1)  
(2, 2, 2, 2, 2, 2)  
(3, 3, 3, 1, 0, 0)  
(3, 2, 1, 1, 1, 0) 
A) (1, 1, 1, 1, 1, 1)
Yes, it is a graph.
We will see that option (C) is not graphic.
Question 60 
The chromatic number of the following graph is _______.
1  
2  
3  
4 