Proof

Question 1

in any graph, nb of odd dergee vertices is even

Answer 1

Handshake lemma

Question 2

simple graph G contains no odd length closed walk => G bipartite

Answer 2

• suppose G connected
• AUB = V
  -AinterB = vide
  -e = uw

Question 3

G graph, e cut-edge; no cycle contains e

Answer 3

contradiction

Question 4

G simple graph, deg(v)>=2 for all v€V, G contains a cycle

Answer 4

P maximum length path

Question 5

Cayley’s Theorem

Answer 5

p: T->C prüfer code functIon
show bijectivity

Question 6

G graph n vertices k edges, comp(G)>=n-k

Answer 6

induction on k

Question 7

G connected on n vertices, |E(G)|>=n-1

Question 8

G a tree, |V(G)| = |E(G)|+1

Question 9

every closed walk of odd length contains an odd cycle

Answer 9

exists repetition

Question 10

Euler theo

Answer 10

=>) contradiction
<=) induction on |E(G)|

Question 11

element u,v de A^k = nb of walks from u to v of k length

Answer 11

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

Question 12

M maximal, M’ maximum |M|>= |M’|/2

Question 13

Hall’s Mariage theorem

Answer 13

=>) f: S -> N(S) matching function
prove injectivity
<=) induction on|A|

Question 14

D digraph, deg(v)>=1 for all v€E => contains a cycle

Answer 14

maximum path

Question 15

every tournament has an Hamiltonian path

Answer 15

induction on |V(T)|

Question 16

if H1 and H2 2 strongly connected components then H1 and H2 do not share any vertex

Answer 16

contradiction

Question 17

H1 and H2 strongly connected components of digraph D, all arcs between H1 and H2 are in the same direction

Question 18

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

Answer 18

<=) contradiction
=>) induction on |V(D)|

Question 19

A tournament T has an Hamiltonian cycle iff T is strongly connected

Answer 19

=>) direct
<=) contradiction

Question 20

H1, H2 blocks, show that |V(H1) ∩V(H2)|<= 1

Answer 20

Contradiction
Maximality => ∃cut vertex
2 cases

Question 21

∀v1,v2∈G, ∃k internally disjoints paths from v1 to v2 => G is k connected

Answer 21

By contradiction

Question 22

G a graph on n>=3 vertices
G 2-connected IFF ∀u,v∈G there exists a cycle containing u and v

Answer 22

=>]
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

Question 23

G a simple graph
X(G) >= n/alpha(G)

Answer 23

contradiction
note : a color class is a inde set

Question 24

G a graph of maximum degree Δ then X(G)<= Δ+1

Answer 24

ordering + argument of greedy coloring (at most Δ in N(vi) )

Question 25

G k-degenerate then X(G)<= k+1

Answer 25

induction on n

Question 26

G k-critical then d(G)>=k-1

Answer 26

Rappel : k-critical := X(G)=K and ∀v X(G-v)<k

contradiction

Question 27

Show that for any graph G there is an ordering of the vertices for which the greedy algo uses exactly X(G) colors

Answer 27

Take a coloring using exactly X(G)

Question 28

G simple graph on n vertices and delta max degree
alpha(G) >= n/(delta+1)

Answer 28

• alpha(G)>= n/X(G) –> mean size of color class
• X(G) <= delta +1

Question 29

G triangle - free graph on n vertices
X(G) <= 2 * racine(n)

Answer 29

delta max degree
*delta <= racine(n)
*delta>racine(n)
N(v) only one color

Question 30

X(G) + X(G barre) <= n+1

Answer 30

induction on n

Question 31

G interval graph
w(G) = X(G)

Answer 31

contradiction : X(G)>w(G)
(we already know X(G)>=w(G))

Question 32

X(G)=k then X(Gm)=k+1

Answer 32

• X(Gm)<=k+1
• X(Gm)< k+1 (contradiction of >=)

Question 33

Somme(size(f)) = 2 |E|
∀f∈F(G)

Answer 33

edge : * boundary walk of 2 faces
* twice in boundary walk of outside face

Question 34

G a plane graph connected

|V(G)|-|E(G)|+|F(G)| = 2

Answer 34

show for multigraphs
* e is a loop
* e is a // edge
* e is neither (contracting)

Question 35

G a simple connnected planar graph with at least 2 edges
|E(G)|<= 3n - 6

Answer 35

size(f)>=3 ∀f∈F(G)

Question 36

n a natural nb
show that there exists a planar graph on n vertices and 3n-6 edges

Answer 36

constructive proof

Question 37

G triangle-free planar graph on n vertices. What is the max amount of edges it can have ?

Answer 37

each face delimited by at least 4 edges

Question 38

prove K3,3 not planar

Answer 38

max nb of edges of triangle free planar graph

Question 39

G planar than G 5-colorable

Answer 39

induction on n
n=1
v st deg(v)<=5
*if deg(v)<=4 : done
* deg(v) =5
Gi,j := graph on vertices of colors i and j

Question 40

G graph admitting a perfect matching M
∀subset U of V(G) :
|odd(G\U)|<=|U|

Answer 40

every vertex of G\U not covered by M|G\U is paired with a vertex of U in M
=> inductive function