Graph theory

Order of a Graph G(V,E)

The number of vertices in a graph = |V|

Size of a Graph G(V,E)

The number of edges in a graph = |E|

Self-loop edge

Start and end vertices are same for the edge

Parallel edges

Edges that connect the same pair of vertices

Incident

Meeting point of an edge and a vertex

Degree of a vertex

The number of edges incident of the vertex, with loops counted twice

Odd degree vertex is called __________

Odd vertex

Even degree vertex is called __________

Even vertex

Null Graph

A graph with no edges

Trivial Graph

It is a null graph with order 1

Multi-Graph

Graphs containing parallel edges and self loops

Simple graph

Graphs containing neither parallel edges nor self loops

The minimum number of edges in a simple connected graph with n vertices is __________

(n-1)

The maximum number of edges in a simple connected graph with n vertices is __________

n(n-1)/2

The total number of simple graphs possible with n vertices and e edges is __________

[n(n-1)/2] C e

The total number of simple graphs possible with n vertices is __________

2^[n(n-1)/2)]

The sum of degrees of all vertices in a graph i.e Σd(|V|) equals to __________

twice of number of edges i.e 2(|E|)

Sum of degrees of all vertices must be an __________ number

even

In a simple connected graph, total number of odd vertices should be __________

even

In a simple connected graph with n vertices, maximum degree of a vertex is __________

(n-1)

Minimum degree of a vertex in a graph G is represented as __________

∂(G)

Maximum degree of a vertex in a graph G is represented as __________

△(G)

The relation between minimum degree and maximum degree of a graph G is __________

∂(G) <= 2|E|/|V| <= △(G) <= (|V| - 1)

Writing degree of all vertices either in increasing order or decreasing order is called __________ of a graph G

Degree sequence ex. 1,1,2,2,3,3

What conditions does a degree sequence need to satisfy to be valid?

1. Maximum degree should be (n-1) where n = number of vertices

2. Sum of degrees of all vertices should be an even number

3. Number of the odd degrees must be even

4. At least two degrees will have same degree

An efficient way to find out whether the degree sequence is valid or not is __________ method

Havel-Hakimi

Is the following degree sequence valid?

5, 3, 3, 3, 2, 2, 2

Valid

Which of the following degree sequence represent a simple non-directed graph?

a) {2, 3, 3, 4, 4, 5}

b) {2, 3, 4, 4, 5}

c) {1, 3, 3, 4, 5, 6, 6}

d) {2, 2, 3, 3}

a) ❌ odd number of vertices

b) ❌ minimum degree should be 4 since |V| = 5

c) ❌ we have 2 vertices with degree 6 i.e is the maximum degree of the graph with 7 vertices hence we cannot have a vertex with degree 1

d) {2, 2, 3, 3}

Which of the following degree sequences cannot represent a simple non-directed graph?

a) {1, 1, 2, 2}

b) {3, 3, 3, 3, 2}

c) {0, 1, 2, 2, 3}

d) {1, 3, 3, 3}

d) {1, 3, 3, 3}

reason: it has an odd number of odd vertices

A non-directed graph contains 16 edges and all vertices are of degree 2. Then the number of vertices in the graph is __________

8

A simple non-directed graph contains 21 edges, 3 vertices of degree 4 and the other vertices are of degree 2. Then the number of vertices in the graph is __________

18

If a simple non-directed graph G contains 24 edges and all vertices are of the same degree then which of the following is false?

a) |V| = 24

b) |V| = 8

c) |V| = 16

d) |V| = 6

d) |V| = 6

reason: if the number of vertices is 6 then degree of each vertex is 8 which is impossible because maximum degree each vertex in a graph with 6 vertices is (n-1) = (6-1) = 5

The largest possible number of vertices in a graph G, with 35 edges and all vertices are of degree at least 3 is __________

23

reason: ∂(G) = 3

∂(G) <= 2|E|/|V|

therefore, |V| = 70/3 ≈ 23

Let G be a simple graph with n vertices. Then the number of edges of G is less than or equal to __________

n(n-1)/2

If the degree sequence is valid for a simple graph G then the sequence is called __________

Graphical

Every vertex is connected to every other vertex in a simple connected graph then the graph is known as __________

Complete graph

A complete graph with n vertices is denoted by __________

Kn

Number of edges in a complete graph with n vertices is __________

[n(n-1)/2]

Degree of each vertex in a complete graph is __________

(n-1)

If the edges that exist in G1 am absent in another G2, and if both G1 and G2 are combined together to form a complete graph, then G1 and G2 are called __________ to each other.

complement

G + G' = __________

Kn

|E(G)| + |E(G')| = __________

|E(Kn)|

|V(G)| + |V(G')| = __________

|V(Kn)|

deg(v1) in G + deg(v1) in G' = __________

(n-1)

If a simple graph G has 4 vertices and has a degree sequence {1, 1, 1, 1}, then the degree sequence in G' is __________

{2, 2, 2, 2}

Number of odd degrees in G and number of odd degrees in G' are __________

Equal

A Cycle graph of order n, must contain a cycle of length __________ , and degree of each vertex should be __________

n, 2

A Cycle graph is denoted by __________ and n is >= __________

Cn

|E(Cn)| = __________ = __________

|V(Cn)| , Length of the cycle

Degree of each vertex v in Cycle graph is __________

2

A Wheel graph is denoted as __________ and n is >= __________

Wn

W4 is derived from __________

C3

Degree of hub vertex in Wn is __________

(n-1)

Degree of any vertex except for the hub vertex in Wn is __________

3

Total number of edges in Wn is __________

2(n-1)

If degree of every vertex is 'k' then it is called a __________ graph

k-regular

Every cycle graph is a __________ -regular graph

2

Total number of edges in a k-regular graph with n vertices is __________

nk/2

__________ graph G(V, E) where vertices V can be divided into two disjoint sets V1 U V2 whose each edge will be from one set to another but not in the same set

Bipartite

A Bipartite graph with vertex sets Vm and Vn is denoted as __________

Km,n

If every vertex of set V1 is connected to every vertex of set V2 then it is called a __________ Bipartite graph

Complete

Total number of edges in a complete bipartite graph Km,n is __________

m*n

Total number of vertices in a complete bipartite graph Km,n is __________

m+n

Minimum number of edges in a bipartite graph Km,n is __________

min{m,n}

Maximum number of vertices in a bipartite graph Kn/2,n/2 is

n^2/4

A bipartite graph should have __________ length cycle

even

A Star graph of n vertices can be defined as __________

K 1,(n-1)

The complement of a star graph of order n, is a __________ graph of __________ vertices and an __________ vertex

complete, (n-1), isolated

A graph or a multi-graph that can be drawn in a plane so that no two edges cross with each other is called __________ graph

Planner

K5 and K3,3 are __________ graphs

Non-planner

A non-planner graph with minimum number of vertices is __________

K5

A non-planner graph with minimum number of edges is __________

K3,3

A planner graph divides the area into connected areas those areas are called __________

Regions