Theorems

Question 1

Hand Shaking Theorem
(The sum of degree of all vertices in G is twice the number of edges)

Answer 1

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

Question 2

An undirected graph has an even no of vertices of odd degree

Answer 2

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

Question 3

In a directed graph sum of indegree of vertices = sum of out degree of vertices = no of vertices

Answer 3

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|

Question 4

Number of edges in a bipartite graph with n vertices is atlmost (n^2/4)

Answer 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

Question 5

The max no of edges in a simple graph with n vertices is n(n-1)/2

Answer 5

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

Question 6

if a graph g(con or not) has exactly 2 vertices of odd degree then there is a path joining these 2 vertices

Answer 6

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

Question 7

In an undirected graph with |V| = v and no loops ST 2E= v^2-v

Answer 7

|E| = n(n-1)/2
2|E| = n^2 - n (replace n with v)

Question 8

Show that in a simple graph with n vertices each vertex has a max degree of n-1

Answer 8

in a complete graph each vertex as the degree of n-1 therefore the max limit of degree is n-1

Question 9

Travelling Salesman

Answer 9

Start somewhere go visit all vertices and come back to the same starting point and choose the lowest weighted edges

Question 10

Fleurys algo

Answer 10

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

Question 11

There is only one path b/w every pair of vertices in a tree

Answer 11

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

Question 12

a tree with n vertices has n-1 edges

Answer 12

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

Question 13

In a tree with 2 or more vertices there are atleast 2 pendant vertices

Answer 13

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

Question 14

In a graph there is only one and only one path b/w every pair of vertices then G is a tree

Answer 14

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

Question 15

a simple graph is connected IFF it has a spanning tree

Answer 15

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

Question 16

For any graph G vertex connec<= edge connec <= min degree of vertex of G

Answer 16

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

Question 17

every connected graph with 3 or more vertices has atleast 2 vertices that are not cut vertices

Answer 17

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

Question 18

the max vertex connectivity of a graph = 2e/n

Answer 18

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

Question 19

a graph is planar iff it can be drawn on a sphere

Answer 19

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

Question 20

Eulers therem on plane graph

Answer 20

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

Question 21

let h be a planar graph without parallel edges on n vertices and e edges where e>=3 then e<=3n-6

Answer 21

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