Proof Flashcards
in any graph, nb of odd dergee vertices is even
Handshake lemma
simple graph G contains no odd length closed walk => G bipartite
- suppose G connected
- AUB = V
-AinterB = vide
-e = uw
G graph, e cut-edge; no cycle contains e
contradiction
G simple graph, deg(v)>=2 for all v€V, G contains a cycle
P maximum length path
Cayley’s Theorem
p: T->C prüfer code functIon
show bijectivity
G graph n vertices k edges, comp(G)>=n-k
induction on k
G connected on n vertices, |E(G)|>=n-1
G a tree, |V(G)| = |E(G)|+1
every closed walk of odd length contains an odd cycle
exists repetition
Euler theo
=>) contradiction
<=) induction on |E(G)|
element u,v de A^k = nb of walks from u to v of k length
statement : sum of walks of length k-1 form u to w for all w€N(v) = sum of walks of length k from u to v
M maximal, M’ maximum |M|>= |M’|/2
Hall’s Mariage theorem
=>) f: S -> N(S) matching function
prove injectivity
<=) induction on|A|
D digraph, deg(v)>=1 for all v€E => contains a cycle
maximum path
every tournament has an Hamiltonian path
induction on |V(T)|
if H1 and H2 2 strongly connected components then H1 and H2 do not share any vertex
contradiction
H1 and H2 strongly connected components of digraph D, all arcs between H1 and H2 are in the same direction
a digraph D is acyclic iff there’s an ordering pn the vertices v1 … vn such that for all i,j = 1…n, i<j, there’s no arc vjvi
<=) contradiction
=>) induction on |V(D)|
A tournament T has an Hamiltonian cycle iff T is strongly connected
=>) direct
<=) contradiction
H1, H2 blocks, show that |V(H1) ∩V(H2)|<= 1
Contradiction
Maximality => ∃cut vertex
2 cases
∀v1,v2∈G, ∃k internally disjoints paths from v1 to v2 => G is k connected
By contradiction
G a graph on n>=3 vertices
G 2-connected IFF ∀u,v∈G there exists a cycle containing u and v
=>]
show a stronger statement : ∀e,f∈E(G), there is a cycle containing both
induction on k (length of shortest path from e to f)
k=2 : adjacent
G a simple graph
X(G) >= n/alpha(G)
contradiction
note : a color class is a inde set
G a graph of maximum degree Δ then X(G)<= Δ+1
ordering + argument of greedy coloring (at most Δ in N(vi) )
