10.2 Graph Terminology and Special Types of Graphs

Question 1

Adjacent vertices?

Incident edge?

Answer 1

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

Question 2

Neighbourhood :

Answer 2

The set of all neighbors of a vertex v of G = (V, E), denoted by N(v), is called the neighborhood of v. If A is a subset of V, we denote by N(A) the set of all vertices in G that are adjacent
to at least one vertex in A. So,
N(A) = ⋃v∈A N(v).

Question 3

Degree of vertex:

Answer 3

The degree of a vertex 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. The degree of the
vertex v is denoted by deg(v).

Question 4

Isolated vertex:

Answer 4

A vertex of degree zero is called isolated. It follows that an isolated vertex is not adjacent
to any vertex.

Question 5

Pendant

Answer 5

A vertex is pendant if and only

if it has degree one. Consequently, a pendant vertex is adjacent to exactly one other vertex.

Question 6

THE HANDSHAKING THEOREM

Answer 6

Let G = (V, E) be an undirected graph with m
edges. Then
2m = ∑ deg(v).
v∈V

(Note that this applies even if multiple edges and loops are present.)

What do we get when we add the degrees of all the vertices of a graph G = (V, E)? Each
edge contributes two to the sum of the degrees of the vertices because an edge is incident with
exactly two (possibly equal) vertices.

analogy between an edge having two endpoints and a handshake involving two hands.

Question 7

Theorem 2:

undirected graph, magnitude of vertices with a certain kind of parity of degree.

and proof:

Answer 7

An undirected graph has an even number of vertices of odd degree.

Let V1 and V2 be the set of vertices of even degree and the set of vertices of odd degree,
respectively, in an undirected graph G = (V, E) with m edges. Then
2m = ∑ deg(v) = ∑ deg(v) + ∑ deg(v).
v∈V v∈V1 v∈V2
Because deg(v) is even for v ∈ V1, the first term in the right-hand side of the last equality is
even. Furthermore, the sum of the two terms on the right-hand side of the last equality is even,
because this sum is 2m. Hence, the second term in the sum is also even. Because all the terms in
this sum are odd, there must be an even number of such terms. Thus, there are an even number
of vertices of odd degree.

Question 8

Terminology for directed edges:

1. Adjacent
   and 2 more terms.

Answer 8

When (u, v) is an edge of the graph G with directed edges, u is said to be adjacent to v and v
is said to be adjacent from u. The vertex u is called the initial vertex of (u, v), and v is called
the terminal or end vertex of (u, v). The initial vertex and terminal vertex of a loop are the
same.

Question 9

degrees for directed edges:

Answer 9

In a graph with directed edges the in-degree of a vertex v, denoted by deg−(v), is the number
of edges with v as their terminal vertex. The out-degree of v, denoted by deg+(v), is the
number of edges with v as their initial vertex. (Note that a loop at a vertex contributes 1 to
both the in-degree and the out-degree of this vertex.)

Question 10

Directed graph number of edges and degrees Theorem:

Answer 10

Let G = (V, E) be a graph with directed edges. Then
∑ deg−(v) = ∑ deg+(v) = |E|.
v∈V v∈V

Question 11

Underlying undirected graph :

Answer 11

There are many properties of a graph with directed edges that do not depend on the direction
of its edges. Consequently, it is often useful to ignore these directions. The undirected graph that
results from ignoring directions of edges is called the underlying undirected graph.

A graph
with directed edges and its underlying undirected graph have the same number of edges.

Question 12

Some Special Simple Graphs

Answer 12

1. Complete Graphs
2. Cycles
3. Wheels
4. n-Cubes

Question 13

Complete Graphs:

Answer 13

A complete graph on n vertices, denoted by Kn, is a simple graph
that contains exactly one edge between each pair of distinct vertices.

Question 14

Non complete:

Answer 14

A simple graph for which there is at least one pair

of distinct vertex not connected by an edge is called noncomplete.

Question 15

Cycles

Answer 15

A cycle Cn, n ≥ 3, consists of n vertices v1, v2, … , vn and edges {v1, v2}, {v2, v3}, … ,
{vn−1, vn}, and {vn, v1}.

Question 16

Wheels:

Answer 16

We obtain a wheel Wn when we add an additional vertex to a cycle Cn, for n ≥ 3, and
connect this new vertex to each of the n vertices in Cn, by new edges.

Question 17

n-Cubes

Answer 17

An n-dimensional hypercube, or n-cube, denoted by Qn, is a graph that has vertices
representing the 2^n bit strings of length n. Two vertices are adjacent if and only if the bit strings
that they represent differ in exactly one bit position.

Question 18

construct the (n + 1)-cube Qn+1

Answer 18

Note that you can construct the (n + 1)-cube Qn+1 from the n-cube Qn by making two copies
of Qn, prefacing the labels on the vertices with a 0 in one copy of Qn and with a 1 in the other
copy of Qn, and adding edges connecting two vertices that have labels differing only in the first
bit.

Question 19

Bipartite Graphs

Definition 6:

Answer 19

A simple graph G is called bipartite if its vertex set V can be partitioned into two disjoint
sets V1 and V2 such that every edge in the graph connects a vertex in V1 and a vertex in V2
(so that no edge in G connects either two vertices in V1 or two vertices in V2). When this
condition holds, we call the pair (V1, V2) a bipartition of the vertex set V of G.

Question 20

Theorem 4 provides a useful criterion for determining whether a graph is bipartite.

and prove it

Answer 20

A simple graph is bipartite if and only if it is possible to assign one of two different colors to
each vertex of the graph so that no two adjacent vertices are assigned the same color.

[ Graph Colourings ]

Question 21

Another useful criterion for determining whether a graph is bipartite is based on the notion
of a path

Answer 21

A graph is bipartite if and only if it is not possible
to start at a vertex and return to this vertex by traversing an odd number of distinct edges. We
will make this notion more precise when we discuss paths and circuits in graphs in Section 10.4
(see Exercise 63 in that section).

Question 22

Complete Bipartite Graphs

Answer 22

A complete bipartite graph Km,n is a graph that has its vertex
set partitioned into two subsets of m and n vertices, respectively with an edge between two
vertices if and only if one vertex is in the first subset and the other vertex is in the second
subset.

see figures for all types of graphs.

Question 23

Matching?

Matched in matching M ?

Maximum Matching ?

Answer 23

matching M in a simple graph G = (V, E) is a subset of the set E of
edges of the graph such that no two edges are incident with the same vertex.

In other words, a
matching is a subset of edges such that if {s, t} and {u,v} are distinct edges of the matching, then s, t, u, and v are distinct.

A vertex that is the endpoint of an edge of a matching M is said to
be matched in M; otherwise it is said to be unmatched.

A maximum matching is a matching
with the largest number of edges.

Question 24

Matching M in a bipartite graph G = (V, E)
with bipartition (V1, V2) is a complete matching from V1 to V2 if

Answer 24

if every vertex in V1 is the
endpoint of an edge in the matching, or equivalently, if |M| = |V1|.

To assign employees to all jobs we
seek a complete matching from the set of jobs to the set of employees.

Question 25

HALL’S MARRIAGE THEOREM

and prove it:

NECESSARY AND SUFFICIENT CONDITIONS FOR COMPLETE MATCHINGS

Answer 25

The bipartite graph G = (V, E) with bipartition
(V1, V2) has a complete matching from V1 to V2
if and only if
|N(A)| ≥ |A| for
all subsets A of V1.

only if : easy
if : strong induction on |V1|

Question 26

Local Area Networks:

Answer 26

Star topology : K 1,n
Ring topology : Cn
Hybrid: Wn
look at the graphs.

Question 27

Interconnection Networks for Parallel Computation

Serial ?

Parallel processing?

Parallel algorithms:

Answer 27

algorithms written to solve problems were
designed to perform one step at a time; such algorithms are called serial.

Parallel processing, which uses computers made up of many separate processors, each
with its own memory, helps overcome the limitations of computers with a single processor.

Parallel algorithms, which break a problem into a number of subproblems that can be solved
concurrently, can then be devised to rapidly solve problems using a computer with multiple
processors. In a parallel algorithm, a single instruction stream controls the execution of the
algorithm, sending subproblems to different processors, and directs the input and output of
these subproblems to the appropriate processors.

Question 28

Interconnection Networks for Parallel Computation

Network types and disadvantages?

Answer 28

Using Kn to connect processors will need large connections not always feasible.
Linear array : Except P1 and Pn all Pi are connected to Pi-1 and Pi+1.
The disadvantage
is that it is sometimes necessary to use a large number of intermediate links, called hops, for
processors to share information.

The mesh network (or two-dimensional array) is a commonly used interconnection network. In such a network, the number of processors is a perfect square, say n = m2. The n processors are labeled P(i, j), 0 ≤ i ≤ m − 1, 0 ≤ j ≤ m − 1. Two-way links connect processor P(i, j)
with its four neighbors, processors P(i ± 1, j) and P(i, j ± 1), as long as these are processors in
the mesh.

Communication between
some pairs of processors requires O(
√n) = O(m) intermediate links. (See Exercise 75.)

Hypercube:
number of processors is a power of 2, n = 2^m. The n processors are labeled P0, P1, … , Pn−1.
two-way connections.Processor Pi is linked to the
processors with indices whose binary representations differ from the binary representation
of i in exactly one bit.
This network balances the number of direct connections for each processor and the number of intermediate connections required so that processors can communicate.
Graph Qm, represents hypercube network with n = 2m processors.

Question 29

Subgraphs :

Answer 29

A subgraph of a graph G = (V, E) is a graph H = (W, F), where W ⊆ V and F ⊆ E. A subgraph H of G is a proper subgraph of G if H ≠ G.

Question 30

Definition 8:

Subgraph Induced:

Given a set of vertices of a graph, we can form a subgraph of this graph with these vertices
and the edges of the graph that connect them.

Answer 30

Let G = (V, E) be a simple graph. The subgraph induced by a subset W of the vertex set V
is the graph (W, F), where the edge set F contains an edge in E if and only if both endpoints
of this edge are in W.

Think of the difference. example18.

Question 31

REMOVING OR ADDING EDGES OF A GRAPH

Answer 31

Given a graph G = (V, E) and an edge
e ∈ E, we can produce a subgraph of G by removing the edge e. The resulting subgraph, denoted
by G − e, has the same vertex set V as G. Its edge set is E − {e}. Hence,
G − e = (V, E − {e}).

if E′ is a subset of E
a subgraph of G by removing the edges in E′ from graph, has the same vertex set V as G. Its edge set is
E − E′.

G + e = (V, E ∪ {e}). // larger graph.
new edge e,
connecting two previously nonincident vertices, to the graph G.

Question 32

EDGE CONTRACTIONS

Answer 32

When u want to remove the edge and not retain the end points as separate vertices in resulting subgraph.

In such a case
we perform an edge contraction, which removes an edge e with endpoints u and v and merges u and v into a new single vertex w, and for each edge with u or v as an endpoint replaces the edge
with one with w as endpoint in place of u or v and with the same second endpoint.

This give new graph G′ = (V′, E′) not subgraph of G.
V′ = V − {u, v}∪{w}
E′ contains the
edges in E which do not have either u or v as endpoints and an edge connecting w to every
neighbor of either u or v in V.

Question 33

REMOVING VERTICES FROM A GRAPH

Answer 33

When we remove a vertex v and all edges
incident to it from G = (V, E), we produce a subgraph, denoted by G − v. Observe that
G − v = (V − {v}, E′),
where E′ is the set of edges of G not incident to v. Similarly, if V′ is a
subset of V, then the graph G − V′ is the subgraph
(V − V′, E′), where E′ is the set of edges of G
not incident to a vertex in V′

Question 34

Union of 2 graphs

Defintition 9 :

Answer 34

The union of two simple graphs G1 = (V1, E1) and G2 = (V2, E2) is the simple graph with
vertex set V1 ∪ V2 and edge set E1 ∪ E2. The union of G1 and G2 is denoted by G1 ∪ G2.