Theorems Flashcards
Hand Shaking Theorem
(The sum of degree of all vertices in G is twice the number of edges)
proof
degree of a vertex is the number of edges incident to it and we know that each edge is incident with exactly 2 vertices meaning that each edge gets counted twice (One at each end) .Thus the sum of the degree of the each vertex in a graph = 2 times the number of edges in it
An undirected graph has an even no of vertices of odd degree
proof
let G=(v,e) be a undirected graph with n number of vertices and e no of edges
let v1,v2… vm be the odd degree vertices
and let v1c,v2c … vk be the even degree vertices
by handshaking theorem we know that
sum of degree of vertices = 2|e|
therefore
1:sum of degree of vertices with odd degree +
2:sum of degree of vertices with even degree =
2|e|
(1)+even number = even number
therefore
(1) is a even number
In a directed graph sum of indegree of vertices = sum of out degree of vertices = no of vertices
proof
in a directed graph G=(V,E) all edges have a direction they point towards
ie: each edge has a initial vertex and a terminal vertex(which contribute to the indegree and out degree) meaning that each edge contributes once for indegree and out degree
thus sum of indegree = SO Out degree = |E|
Number of edges in a bipartite graph with n vertices is atlmost (n^2/4)
let G=(V,E) be a bipartite graph and v1 and v2 the 2 distinct subsets of the vertices
and let |v| = n and the number of vertices in v1 are x , then the number of vertices in v2 is n-x
to find the max no of edges we need to find the complete bipartite of the graph ie) vertices in v1 are connected to all vertices in v2 meaning |e| = x>(n-x)
now we need to find the value of x
by calculus F(X)=nx-x^2
1” =n-2x
2” =-2
when 1” f(x)= n-2x
x=n/2
hence f(x) is max when x=n/2
therefore max no of edges required = f(n/2)
=n*n/2-(n/2)^2
=n^2/2-n^2/4
=n^2/4
The max no of edges in a simple graph with n vertices is n(n-1)/2
proof
first lets consider a complete graph Kn with n vertices
in a complete graph each vertex is adjacent to all other distince vertices in the graph
ie: each vertex as a degree of (n-1)
and total degree of the graph is n(n-1)
and we know from the handshaking theorem that
sum of degrees of vertices in a graph = 2|E|
therefore no of edges in a complete graph is N(n-1)/2
if a graph g(con or not) has exactly 2 vertices of odd degree then there is a path joining these 2 vertices
proof
case 1:let G be connected
take 2 vertices of odd degree v1 and v2
and since we know there are a even number of graphs with odd degrees then there is clearly a path b/w v1 and v2
In an undirected graph with |V| = v and no loops ST 2E= v^2-v
|E| = n(n-1)/2
2|E| = n^2 - n (replace n with v)
Show that in a simple graph with n vertices each vertex has a max degree of n-1
in a complete graph each vertex as the degree of n-1 therefore the max limit of degree is n-1
Travelling Salesman
Start somewhere go visit all vertices and come back to the same starting point and choose the lowest weighted edges
Fleurys algo
Steps
check whether graph is connect
make sure all vertices are of even degree
start at adjcent vertex and choose vertices that dont break the circuit
There is only one path b/w every pair of vertices in a tree
let T be a tree which is connected and contains no cycles
suppose there existed more than one path existed b/w every pair of vertices
then the union of these two distinct path will contain a circuit
but we know a tree which doesnt have cycles
hence its a contradiction to the assumption
hence there is a unquie path b/w every pair of vertices
a tree with n vertices has n-1 edges
We will use mathematical Induction hypothesis to proove this theorem
*show cases with 0,1,2 edges and verify the arguement
the result is true for these cases
assume the result is true for |E|=k
to prove the result is true for |E|=k+1 edges
the removal of u v from t will obtain us 2 subtrees
let t1 and t2 be the subtrees
the induction hypothesis is truse since it contains less than k+1 edges
*add 2 equations
and hence the proof
In a tree with 2 or more vertices there are atleast 2 pendant vertices
proof
let T be a tree with n vertices where n>=2 clearly T consis of n-1 edges
clearly T consist of n-1 edges
hence the degree of all vertices is twice the number of edges
ie: 2(n-1) degree is divied among the vertices
since no vertex can be 0 degree here
2n-2
2n-1-1
there must be 2 vertices of degree 1 hence the proof
In a graph there is only one and only one path b/w every pair of vertices then G is a tree
Assume that in graph g there is only one path b/w ever pair of vertices
Tp G is a tree
we have to show that there is no circuits in G
suppose G has a circuit then there would exist more than one path b/w any pair of vertices let a nd b be the 2 vertices which are connected by two disntince paths p1 and p2 which is a contradication to our assumption
hence our assumption is wrong
a simple graph is connected IFF it has a spanning tree
suppose that G is a simple graph which has a spanning tree T ie V T = V G
T contains every vertex of G
also there is a path b/w any two of its vertices
spanning tree T is a subgraph of G , there is a path b/w any two of its vertices hence G is connected
For any graph G vertex connec<= edge connec <= min degree of vertex of G
Let G be a connected Graph
first we proove edge connec <= min degree of vertex of G
let v be the smalles degree vertex
edges incident to v are to be removed from g to isolate the vertex thus the removal of E(v) disconnects the graph
it is observed that deletingall neightbours of a fixed vertex of minimal degree disconnects G and deleting all the edges that have a fixed vertex of minimum degree as an end point disconnects G
vertex connec<= edge connec
there exisst a cut set of S of G containg edge conc edges of G
suppose S partion the set of vertices into disjoint subsets v1 and v1
atmost edge connc end points of the edge in S lie in each of v1 and v2
thus by remvoing atlmost theta vertices from either v1 or v2 that are incident with the edge in s all the edges in s will be removed from G leaving it disconnected
every connected graph with 3 or more vertices has atleast 2 vertices that are not cut vertices
lets g be the graph with n>=3
and let T be the spanning tree of G
the spanning tree has 2 pendant vertices v1 v2 which has one degree making it a non cut vertex
therefore T-v1 v1 wont disconnect T
and just like that G-v1 -v2 wont disconnect G
the max vertex connectivity of a graph = 2e/n
let g bet the graph
we know sum of all degree of vertices is 2|e|
and the average degree of vertices is 2e/n
therefore prooven
a graph is planar iff it can be drawn on a sphere
proof
lets get the stereographic projection of a sphere on a plane
mark a point s on the place where the sphere is incident to the plane
then mark a line from s to the top
make it as N
lets take a point p on the plane to N
we mark the line intersecting the sphre with p 0
and with this we can see the 1 to 1 coorespondance of this
and from this we can see that a graph dra
Eulers therem on plane graph
proof
we a re using mathematical induction for this one
m=n=1f=1
=2
m=1 n=2 f=2
Assumin that the therem is true for m-1 edges
take a graph G
if it is a tree the number of vertices =n
edhes = n-1
n=n
m=n-1
f=1
n-m+f= n-n+1+1=2
in the case of G being a graph ie have a cycle
h=g-e
M-1
n=n=
f-1
n-m+f== n-m-1+f-1
n-m+f=2
let h be a planar graph without parallel edges on n vertices and e edges where e>=3 then e<=3n-6
n-m+f
proof
take h as the planar graph
f be no of faces
n is the number of vertices
and mi the no of edges on the boundry
mi>= 3
3f<= sumation of mi
summ of mi <= 2e
3f <= 2e
