Problem 1.

(a) State Dirac’s theorem.
(b) Prove that a connected graph $G$ has an Euler circuit if and only if every vertex has even degree.
(c) Give an example of a graph that contains an Euler circuit but does not contain a Hamilton cycle. Justify your answer.
(d) Let $G$ be a connected graph in which all vertices have even degree except two which have odd degree. Prove that there is a walk in $G$ that uses every edge exactly once.

Problem 2.

(a) Define the Turán graph $T_r(n)$. How many edges are there in $T_3(11)$ ?
(b) Show that if $G=(V, E)$ is an $r$-partite graph of order $n$ then $|E| \leqslant\left|E\left(T_r(n)\right)\right|$.
(c) Define $\operatorname{ex}(n, H)$, where $H$ is a graph and $n \geqslant 1$ is an integer.
(d) Prove that
$$\pi(H)=\lim _{n \rightarrow \infty} \frac{\operatorname{ex}(n, H)}{\left(\begin{array}{l} n \ 2 \end{array}\right)}$$
is well-defined.
(e) Show that if $\Delta(H) \neq 0$ then $\pi(H) \leqslant 1-\frac{1}{\Delta(H)}$.

UprivateTA™为您的留学生涯保驾护航。

# MATH0029 Graph Theory and Combinatorics

 Year: 2023-2024 Code: MATH0029 Level: 6 (UG)/7(PG) Normal student group(s): UG Year 3 Mathematics degrees Value: 15 credits (= 7.5 ECTS credits) Term: 1 Assessment: 90% examination 10% coursework Normal Pre-requisites: MATH0057 recommended Lecturer: Dr J Talbot

## Course Description and Objectives

The course aims to introduce students to discrete mathematics, a fundamental part of mathematics with many applications in computer science and related areas. The course provides an introduction to graph theory and combinatorics, the two cornerstones of discrete mathematics. The course will be offered to third or fourth year students taking Mathematics degrees, and might also be suitable for students from other departments. There will be an emphasis on extremal results and a variety of methods.

## Recommended Texts

B Bollobás, Modern Graph Theory (Springer); B Bollobás, Combinatorics (Cambridge University Press).

## Detailed Syllabus

• Binomial coefficients, convexity. Inequalities: Jensen’s, AM-GM, Cauchy-Schwarz. Graphs, subgraphs, connectedness, Euler circuits, cycles, trees, bipartite graphs and other basic concepts. Vertex colourings. Graphs with large girth and large chromatic number.
• Extremal graph theory: Dirac’s theorem. Ore’s theorem. Mantel’s theorem. Turán’s theorem (several proofs including probabilistic and analytic). Kövári-Sós-Turán theorem with applications to geometry. Erdős-Stone theorem. Stability. Andrásfai-Erdős-Sós theorem.
• Set Systems: Basic definitions; set systems and the discrete cube. Chains and antichains. Sperner’s lemma. The LYM inequality. Intersecting families; the Erdos-Ko-Rado theorem (probabilistic and compression proofs). Isoperimetric problems: local LYM inequality, Kruskal-Katona theorem. The linear algebra method: Fisher’s inequality, RayChaudhuri-Wilson theorem.
• Ramsey theory: Ramsey’s theorem. Upper and lower bounds including probabilistic ideas. Schur’s Theorem. Fermat’s Last Theorem is false in \$\mathbb{Z}_p

Fourier analysis代写

## 离散数学代写

Partial Differential Equations代写可以参考一份偏微分方程midterm答案解析