Neighborhood and Special Graphs

Question 1

Two vertices u and v in an undirected graph G are called adjacent(or neighbors) in G if e = {u, v}, the edge e is
called incident with the vertices u and v. The edge e is also said to connect u and v. The vertices u and v are called
endpoints of the edge {u, v}.

Answer 1

NEIGHBORHOOD

Question 2

The _________ in an undirected graph is the number of edges incident with it, except that a loop
at a vertex contributes twice to the degree of that vertex. It is denoted by deg(v), where v ∈ V (G).

Answer 2

DEGREE OF A VERTEX

Question 3

• A vertex of degree zero is called________

Answer 3

isolated vertex.

Question 4

A vertex of degree one is called ________

Answer 4

pendant vertex.

Question 5

For a graph G of a given order n, what is the possible value of m?
n = 1 −→ m =
n = 2 −→ m =
n = 3 −→ m =
n = 4 −→ m =
Thus,
m = (n2) =

Answer 5

m = 0
m = 1
m = 3
m = 6

=n(n−1)/2

Question 6

(FFTGT)

Answer 6

FIRST FUNDAMENTAL THEOREM OF GRAPH THEORY

Question 7

Corollary 2.4. Every graph contains an even number of odd vertices (Equivalently, the number of vertices of odd degree
is even).
Give the Proof.

Answer 7

Proof. Let V_o=set of odd vertices
V_e=set of even vertices
By FFTGT,
Summation of
v_i∈V (G) deg(vi) = 2m
Summation of v∈V_o deg(v) + Pv∈Ve P deg(v) = 2m

v∈V_o deg(v) = 2m − Pv∈Ve P deg(v)
v∈Vo
deg(v) is always even.
Thus, |Vo| is even.

Question 8

Definition 2.5. When (u, v) is an edge of the graph G with directed edges, v is said to be adjacent from u. The vertex
u is called the_______ of (u, v), and v is called the ________ of (u, v). The ________ and ________ of a loop are the same.

Answer 8

initial vertex
terminal or end vertex

initial vertex& terminal
vertex

Question 9

In a graph with directed edges, the ______ of a vertex v, denoted by deg − (v), is the number of edges
with v as their terminal vertex. The ________ of v, denoted by deg + (v), is the number of edges with v as their initial
vertex. A loop at a vertex contributes 1 to both the _____and ______of this vertex.

Answer 9

in-degree
out-degree

in-degree & out-degree

Question 10

SPECIAL GRAPHS
A ________ is a simple graph, denoted by K_n where in n is the number of vertices in a graph, in
which any two vertices are adjacent. A _______ has no loops and every two vertices share exactly one edge. The
number of m edges in a ________ with n number of vertices is given by,

m = (n2) = n(n − 1)/2

Answer 10

Complete Graph K_n
complete graph

Question 11

Definition 3.2. A _________ is a simple graph with 3 or more vertices whose vertices can be arranged in a cyclic
sequences. It is only possible when n ≥ 3.

Answer 11

Cycle C_n
cycle graph

Question 12

Definition 3.3. A ______ is a simple graph whose vertices can be arranged in a linear sequence in such a way that
two vertices are adjacent if there are consecutive in the sequence and are non adjacent otherwise. It is only possible when
n ≥ 1.

Answer 12

Path P_n
path graph

Question 13

Definition 3.4. A _________ is obtained by adding an additional vertex to the cycle Cn for n ≥ 3 and connect this new
vertex to each of the n vertices in Cn, by new edges.
Terms:
hub −→
spokes −→
rim −→

Answer 13

Wheels Wn
wheel graph

hub −→ newvertex
spokes −→ newedges
rim −→ thecycleinthewheels

Question 14

Definition 3.5. A graph G is a ___________ if its vertex can be partitioned into subsets X and Y so that every edge
has one end in X and one end in Y . If every vertex in X is joined to every vertex in Y , then G is called a ___________

Answer 14

Bipartite Graph K_m,n

bipartite graph

complete
bipartite graph

Question 15

Values of n that are bipartite:
(1) K_n =⇒
(2) C_n =⇒
(3) W_n =⇒

Answer 15

Values of n that are bipartite:
(1) K_n =⇒ n = 2
(2) C_n =⇒ n ≥ 4 for every n is even natural number
(3) W_n =⇒ NONE