Adv. Graph Theory – Final Exam Suggestion

1. (a) Define with example:
Pseudo graph, complete graph ….
(b) Draw graph (Set of vertex & edges are given)
(c) Deleted sub-graph related math.
2. (a) Find adjacency for the following graph
(b) Draw graph whose adjacency matrix is given
(c) Definition
3. (a) Graph isomorphism. (Definition; Math)
4. (a) Explain with example
Planar graph, Degree of a region, Bipartite graph, Directed graph, etc.
(b) Determine whether the given walk in the following graph is (i) Path, (ii) a trail, (iii) a closed walk, (v) a circuit, (vi) a cycle.
5. State & prove Euler’s theorem. Verify theorem.
Math V-E+R=2
6. (a) If T is a tree with n vertices than it has precisely n-1 edges. (Theorem 3)
(b) Theorem 1
(c) Theorem 9
7. (a) Theorem 11
(b) Theorem 6


Let G1=G1(V1,E1) and G2=G2(V2,E2) be two graphs. Then G1 said to be isomorphic to G2 if there is a one-to-one function ⱷ from v1 into v2 such that

(i)                  If uv is an edge in E1 then  ⱷ(u) ⱷ (v) is an edge in E2 and

(ii)                Every edge in E2 has the form ⱷ (v) ⱷ (v) for same edge in uv € E1

Vertex Degrees

An edge e of a graph G is said to be incident with vertex v, if v is an end vertex of e.

Two edges e and  f which are incident with a common vertex v are said to be adjacent.