Scribd
Upload
23 views3 pages

Havel-Hakimi Theorem in Graph Theory

This document contains 20 questions about graph theory concepts for a mathematics assignment. The questions cover topics such as: 1) Drawing graphs with 3 vertices and determining the number of graphs for n vertices where n=3,4,5 2) Finding adjacency and incidence matrices of graphs 3) Determining properties of graphs like being simple, bipartite, or complete 4) Applying the Havel-Hakimi theorem to degree sequences 5) Checking if graphs are isomorphic and properties of isomorphic graphs

Uploaded by

Shiva Poojith
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
23 views3 pages

Havel-Hakimi Theorem in Graph Theory

This document contains 20 questions about graph theory concepts for a mathematics assignment. The questions cover topics such as: 1) Drawing graphs with 3 vertices and determining the number of graphs for n vertices where n=3,4,5 2) Finding adjacency and incidence matrices of graphs 3) Determining properties of graphs like being simple, bipartite, or complete 4) Applying the Havel-Hakimi theorem to degree sequences 5) Checking if graphs are isomorphic and properties of isomorphic graphs

Uploaded by

Shiva Poojith
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Department of Mathematics, IITM

MA2130 – Graph Theory


Assignment 1

(1) How many graphs can be drawn with 3 vertices? Sketch the graphs.
(2) Determine the number of graphs on n vertices, where n = 3, 4, 5.
(3) Find the adjacency matrix and the incidence matrix of the following graph.

(4) Determine the number of edges in Kn and Kp,q .


(5) Give the geometric representation for the following graphs:
(a) G1 = (V1 , E1 ) where V1 = {a, b, c, d} and E1 = {aa, ab, ac, ad, bd, bb}.
(b) G2 = (V2 , E2 ) where V2 {a, b, c, d} and E2 = {ab, ba, ac, ca, ad, da, db}
(c) G3 = (V3 , E3 ) where V3 = {a, b, c, d} and E3 = {ab, ac}.
Which the above graphs are (a): Simple, (b): bipartite, (c): complete, (d): Multi-
graph.
(6) Using Havel-Hakimi theorem, determine which of the following are graphical. Sketch the
graphs in all the possible cases.
(a) (5, 5, 3, 2, 1)
(b) (6, 5, 4, 3, 2, 1)
(c) (1, 1, 1, 1, 1, 1)
(d) (4, 3, 3, 2, 2)
(7) Consider the sequence S = (d1 , d2 , · · · , dn ) such that di = k , 1 ≤ i ≤ n. For what values
of k and n is the sequence S graphical?
2

(8) Does there exist a graph with degree sequence (d1 , d2 , · · · , dn ) such that
Pn
(a) i=1 di =even.
Pn
(b) i=1 di =odd.

(c) di 6= dj for all i 6= j.


Justify your answer with proper reasons.
(9) Show that the sequence S = (d1 , d2 , · · · , dn ) is graphical iff the sequence (n − 1 − dn , n −
1 − dn−1 , · · · , n − 1 − d2 , n − 1 − d1 ) is graphical.
(10) Determine whether the following graphs are isomorphic or not:

(11) show that the isomorphic relation on graphs ∼


= between graphs is an equivalence relation.
(12) Sketch all non-isomorphic graphs on n = 3, 4, 5 vertices. Can you say anything about
the number of non-isomorphic graphs on n vertices?
(13) Show that G1 ∼
= G2 iff Gc1 ∼
= Gc2 .
(14) Give an example of a graph with 5 vertices which is isomorphic to its complement.
3

(15) Does there exist a self complementary graph with n = 2, 3?


(16) Let G be a self complementary graph. Show that number of vertices of G is either 4k or
4k + 1 for some natural number k.
(17) How many self complementary graphs are there on 5 vertices upto isomorphism?
(18) Let G1 = (V1 , E1 ) be isomorphic to G2 = (V2 , E2 ). Does there always exist v ∈ V1 and
u ∈ V2 such that G1 \ {v} and G2 \ {u} are isomorphic? Is the converse true?
(19) Consider the following graph G.

(a) Find G \ U where U = {v1 , v3 , v5 , v7 }


(b) Find G \ F where F = {e1 , e3 , e4 , e6 , e8 , e10 }
(c) Find G[U ]
(d) Find G[F ]
(e) Does there exist a subgraph of G isomorphic to K3 , K4 ?
(20) Let G = (V, E) be a graph with n vertices and Gc be its complement.
(a) Show that for each v ∈ V , dG (v) + dGc (v) = n − 1 where dG (v) is the degree of
vertex v in graph G.
(b) Suppose there exists exactly one vertex v ∈ V such that dG (v) is even, find the
number of vertices of G whose degree is odd.
(c) Sketch all non isomorphic on 5 vertices.

You might also like