Mathematics Homework Assignment: Questions 6, 7, and 11 Solutions

This mathematics assignment provides detailed solutions to three key questions. Question 6 focuses on Tutte's theorem, explaining its necessary and sufficient conditions for perfect matching in graphs and illustrating with an example. Question 7 delves into Menger's theorem, proving it for vertices u and v with a foreign route k, and providing a step-by-step explanation using separators and connectors. Question 11 examines geometric progressions and Fibonacci series, demonstrating the limit consideration and derivation to find the value of phi. The assignment includes references to relevant websites for further understanding and proofs for each theorem and concept.

Running head: MATHEMATICS
MATHEMATICS

2
MATHEMATICS
Table of Contents
Question no 6.............................................................................................................................2
Question no 7.............................................................................................................................3
Question no 11...........................................................................................................................4
Reference list..............................................................................................................................5

3
MATHEMATICS
Question no 6.
In a graph to match perfectly, it is necessary to have all the vertices touched or used. Tutte"s
theorem always signifies towards matching with perfection. Tutte's theorem can perfectly
match the graph which contains edges not joined. A graph which is not directed can be
represented by G(V, E). Let M is a subset of E. Tutte"s theorem problem is based on:
Let us consider a set s arbitrarily. Let the unique element be C-S. In C to find a maximum
match, one vertex should not match. Let us consider that S subset of V.Let us match it with a
single vertex in S.So the necessary condition is
|s|>=q(G-S).where q represents no of odd components in G.(people.math.gatech.edu, 2019)
The sketch gives proof that it is a sufficient condition. Phi or null is not an even set in G.And
the odd set is |v(G)|. The maximal wrong edge can determine the bad in the complement
graph of G, a method of searching bad set and its formation. There are three claims to
commemorate the three points. The lousy set with the implementation of three claims is
shown below.

4
MATHEMATICS
Question no 7.
Menger”s theorem for the vertices u and v where u is towards v and k is a foreign route or an
intersection is given below,
We consider that there is a zero edge in a single vertex. Let us consider the graph to be named
as G where the route k is defined in a set S.S can also be termed as a separator. We consider
the route of u to v to be disjoint. Menger's theorem gives it with a small statement that the
smallest size of the separator separating u and v will be equal to the highest size of the
connector connecting u and v.Let x,y belongs to the graph G.then we could formulate the
relation G-{x,y}.UV separator is equivalent to x,y separator.Let us assume that e be an edge
of G then G-e holds by implying induction theorem.G-e also contains the different route of
minimum size k.In this case, G-e also holds the connector connecting u and v which is of size
k. We assume that sis of size k-1.In case it is lesser it would have been a good enough
separator, which is separating u and v.G-s contains a path including UV through the edge
e.In this case, S will alone be a minimal separator of G.Let v1 and v2 be the former and latter
vertex of such path. In this case, we may conclude that v1 can be reached from u and v2 can
be reached from v and cannot be reached from U. Let S1 be S union of v1.(algo.inria.fr,2019)
Where S1=SU{v1}.uS1 is a separator in G-e.T could also be concluded as a separator of
UV.Considering k to be of least size in T.Now G-e holds the connector c1 which is an uS1
connector inhibiting size k. This size exhibits that the endpoints should be S1 of the path.
Now considering similarly that S2=SU{v2}.aThe minimal size should be k of the separator
separating S2v.S2v connector should be called c2 of size k. Hence similarly, we would
continue the whole thing and consider the route starting with S2. We will continue the
process till we could see the disjunction of S1 from G.All the route is in c1 is disconnected
from c2 in the interiors. Hence by concatenation process UV connector is claimed to be of
size k where e=(v1,v2)

5
MATHEMATICS
Below is the graph is given to prove the process:
Question no 11.
Simpler equations which are linear could be Geometric progressions, where X0=1 and
X(n+1)=aXn.
Also we may write that X0,X1,X2…….=a0,a1,a2,a3……….where a is a positive integer.
The series can also be generated as X(n+1)/Xn=a; the series is in the cumulative ratio of a.
To write this in a limit where a is constant, we may form:
lim(n->infinity)(Fn+1/Fn)=phi.
Where F is the Fibonacci series.
The limit consideration is must to find a series.
F(n+1)/Fn is equivalent to phi as well as Fn/F(n-1) is equivalent to phi.
Also we have
F(n+1)=Fn+F(n-1)...........(1)
When we divide (1) by Fn we have
F(n+1)/F(n)=1+F(n-1)/F(n)
Thai is equal to phi=1+phi(where n is tending towards infinity)
phi^2-phi-1=0 which evaluates to an answer
(1+(5)^½)/2 or (1-(5)^½)/2,a rational number.

6
MATHEMATICS
Reference list
Websites
algo.inria.fr (2019), algo, retrieved from:
http://algo.inria.fr/flajolet/Publications/book070503.pdf (Retrieved on: 25.01.2019)
people.math.gatech.edu (2019), people, retrieved from:
http://people.math.gatech.edu/~ecroot/recurrence_notes2.pdf(Retrieved on:
26.01.2019)