Graph Theory Flashcards
Graph consists of ?
Vertices and edges
Undirected graph?
Edges have no direction
degree of a vertex
No. of vertices adjacent to it
In degree of a vertex
No. of vertices directed towards a particular vertex
Out degree of a vertex
No. of vertices directed away from a particular vertex
Sum of degree=
2*no. of edges
In directed , sum of out degree=
Sum of in degree = no. of edges
outgoing edges denoted by
-
incoming edges denoted by
+
Undirected graph types
Simple graph and Multigraph
Simple graph
No parallel edge, no self loop
Multigraph
Parallel edges and self loop present
Self loop degree=
2
If n vertex simple graph, max and min degree
max-n-1
min-0
If n vertex multigraph, max and min degree
max-infinite
min-0
Null graph
0 edges
Complete graph
All edges in a simple graph
no. of edges=n(n-1)/2
Min and max edges in a complete graph
both n(n-)/2
min and max edges in null graph
0
n-regular graph
all vertices have degree n
for k regular graph no. of edges
e=(k*n)/2
Complete graph with n vertices can be represented as n-1 regular graph
yes
Every cycle graph is a
2-regular graph
Cycle graph is not possible for
vertices less than or equal to 2
Cycle graph Cn (2-regular graph with n vertices)
n vertices, n edges
Wheel graph
Using Cn-1 graph and adding 1 vertex in middle
For wheel graph
E=2*(n-1)
Bipartite graph
Two groups m & n , no vertex b/w the members of same group
In bipartite graph m U n =
V
How to verify if graph is bipartite
BFS
m intersection n for bipartite
empty set (phi)
m can be anything but
empty set or phi
n can be anything but
empty set or phi
Which graph can never be bipartite
if it contains odd cycle
Min. vertex for bipartite
2
Min. edges for bipartite
0
Complete bipartite graph
When all possible edges present in bipartite graph
K2,4
Total edges = 8
K m,n
edges= m.n
vertices=m+n
Suppose you have 10 vertices, max edges complete bipartite =
when divided in half=5*5=25 edges
Min. edges in bipartite graph
0
Min. edges in complete bipartite graph with n vertices
(n-1).1
Min edges in complete bipartite graph with m and n groups
m.n
Max edges in bipartite graph
m.n
Star graph edges with n vertices
n-1
Planar graph
Draw graph w/o crossing any edges(can be represented in one plane)
From which complete graph are all complete graphs non planar
K5
Non planar requires least how many vertices
5 (one edge causes non planarity, if we remove becomes planar)
In complete bipartite graph non planarity starts from
K3,3(one edge causes non planarity, if we remove becomes planar) so K3,4 K4,4 all are non planar
Non planarity starts from min. vertices
min. edges
V-5 (K5)
E-9 (K3,3)
A graph G is planar if and only if
it does not contain subgraph which is subdivision of K5 or K3,3
Subdivision means
Same structure, only vertices added inside edges
See question on copy
Regions or faces
Every planar graph is divided into some regions
Degree of a region
No. of edges it is bounded by
Every edge is used twice in making regions
True
Sum of degree of regions =
2*no. of edges
See question
Euler formula(Connected graph)
|V| + |R| = |E| + 2
Euler formula(disconnected graph)
|V| + |R| = |E| + k + 1 (k-no. of connected components)
For n vertices how many simple graphs possible
2^(n(n-1)/2)
Average degree
Sum of degree/ no. of vertices
Average degree bounds
Min degree <= Avg degree <= Max degree
Average degree
2 |E| / |v|
