Graph theory 4th sem( cu)
48 videos • 9,713 views • by by msc mathematics
1
in a tree, any 2 vertices are connected by a unique path
msc mathematics
Download
2
if G is a tree, E=v-1
msc mathematics
Download
3
every non trivial tree has at least two vertices with degree one
msc mathematics
Download
4
A cut edge e of G is an cut edge of G if and only if e is contained in no cycle of G
msc mathematics
Download
5
a connected graph is a tree if and only if every edge is a cut egde
msc mathematics
Download
6
Every connected graphcontain a spanning tree
msc mathematics
Download
7
if G is connected, then e≥v-1
msc mathematics
Download
8
T be a spanning tree of a connected graph G & let e ∈ G & not in T.Then T+e is a unique cycle.
msc mathematics
Download
9
t is spanning tree of G (i) the cotree contains no bond of G(ii) T`+ e contains a unique bond of G.
msc mathematics
Download
10
A vertex v of a tree G is a cut vertex of G if and only if d(v) greater than 1.
msc mathematics
Download
11
If e is a link of G, then τ(G)=τ(G-e)+τ(G·e).
msc mathematics
Download
12
recursive calculation of τ(G)
msc mathematics
Download
13
τ(Kn)=n^(n-2)
msc mathematics
Download
14
Any spanning tree T*= G[{e1, e2, ... ,ev-1}] constructed by Kruskal's algorithm is an optimal tree.
msc mathematics
Download
15
K ≤ K' ≤ δ
msc mathematics
Download
16
A graph is 2-connected ⟺ any 2 vertices of G are connected by at least two internally-disjoint paths
msc mathematics
Download
17
If G is 2-connected, then any two vertices of G lie on a common cycle.
msc mathematics
Download
18
If G is a block with v ≥ 3, then any two edges of G lie on a common cycle.
msc mathematics
Download
19
menger's theorem
msc mathematics
Download
20
Connectivity problem
msc mathematics
Download
21
The graph Hm, n is m connected
msc mathematics
Download
22
The graph Hm,n is m connected(explained )
msc mathematics
Download
23
A non empty connected graph is eulerian if and only if it has no vertices of odd degree
msc mathematics
Download
24
A connected graph has an euler trial if and only if it has atmost two vertices of odd degrees
msc mathematics
Download
25
If G is hamiltonian then, for every nonempty proper substet S of V then w(G-S)≤ISI
msc mathematics
Download
26
If G is a simple graph with v ≥ 3 and δ ≥ v/2, then G is hamiltonian.
msc mathematics
Download
27
G be a simple graph,u&v nonadjacent vertices,d(u)+d(v)≥v.Then G is hamiltonian⟺ G+uv is hamiltonian.
msc mathematics
Download
28
c ( G) is well defined.
msc mathematics
Download
29
A simple graph is hamiltonian if and only if its closure is hamiltonian. ·
msc mathematics
Download
30
G│degree sequence(d1,...,dv),d1≤... ≤dv│v≥ 3│no value of m≤v/2,dm≤m &d(v-m)≤v-m→G is hamiltonian.
msc mathematics
Download
31
If G is a nonhamiltonian simple graph with v ≥3, then G is degree-majorised by some Cm,v
msc mathematics
Download
32
G simple graph│v≤3│e›v-1€2+1│G hamiltonian.only nonhamiltonian with v & (v-1€2)+1 edges→C1,v & C2,5
msc mathematics
Download
33
If G is eulerian, then any trail in G constructed by Fleury's algorithm is an Euler tour of G.
msc mathematics
Download
34
A matching M in G is a maximum matching if and only if G contains no M-augmented path
msc mathematics
Download
35
G be a bipartite graph.Then G contains a matching that Saturates every vertex in x ⟺│N(s)│≥│s│∀ s⊂X
msc mathematics
Download
36
MARRIAGE THEOREMif G is a k regular bipartite graph with K›0,then G has a perfect matching
msc mathematics
Download
37
In a bipartite graph,number of edges in maximum matching = number of vertices in a minimum covering
msc mathematics
Download
38
TUTTE'S THEOREM G has a perfect matching if and only if o(G-s)≤|s|
msc mathematics
Download
39
every three regular graph without cut edges has a perfect matching
msc mathematics
Download
40
G not an Odd cycle ⇒2 edge colouring & both colours are represented at each V of degree at least 2
msc mathematics
Download
41
C optimal and u incident with 2 j colour and not any i colour then component of G[Ei U Ej]&u is odd
msc mathematics
Download
42
if G is a bipartite graph, then X'=Δ
msc mathematics
Download
43
VIZING'S THEOREMif G is a simple graph, then X'=Δ or X'=Δ+1
msc mathematics
Download
44
a set S ⊂V is an indpndnt set of G ⟺ V\S is a covering of G
msc mathematics
Download
45
α+β=v
msc mathematics
Download
46
M be a matching & K be a covering st │M│=│K│. Then M is a maximum matching & K is a minimum covering
msc mathematics
Download
47
If D is strict and min{δ-, δ+}› v/2 › 1, then D contains a directed Hamilton cycle
msc mathematics
Download
48
Calicut University MSc mathematics 4th semester graph theory 2022 question paper and answers
msc mathematics
Download