Riemann surface
matlab

Determine the value of $\operatorname{ex}\left(n, K_{1, r}\right)$ for all $r, n \in \mathbb{N}$.

Solution: We would like to determine how many edges a graph $G$ on $n$ vertices can have before a $K_{1, r}$ subgraph is forced. Note that $G$ has a $K_{1, r}$ subgraph if and only if $\Delta(G) \geq r$. Thus, we must determine the maximum number of edges $G$ can have and still maintain $\Delta(G)<r$. We consider two cases:

Case 1: $n \leq r$. Clearly, if $n \leq r$, we must have $\Delta(G)r$. In this case, we try to draw edges on the vertices of $G$ so that $d(v)=r-1$ for all $v \in V(G)$. While it may not be possible to draw an $r$-1-regular graph on $n$ vertices, we are able to draw $\left\lfloor\frac{(r-1)-n}{2}\right\rfloor$ edges. Thus $\operatorname{ex}\left(n, K_{1, r}\right)=\left\lfloor\frac{(r-1) \cdot n}{2}\right\rfloor$.

Given $k>0$, determine the extremal graphs without a matching of size $k$.

Solution: Let $n \in \mathbb{N}$ and $k>0$. We will consider two cases:
Suppose $n<2 k$. The complete graph $K_{2 n}$ will certainly have no matching of size $k$. This graph $K_{2 n}$ has $\left(\begin{array}{l}n \ 2\end{array}\right)$ edges, and we certainly cannot better. Thus $K_{2 \mathrm{n}}$ is the extremal graph in this case.

Suppose $n \geq 2 k$. We construct the extremal graph in the following way: First, construct a $K_{k-1}$. Then, draw an edge from each of the remaining $(n-k+1)$ vertices to each of the edges in the $K_{k-1}$. Then every edge in a maximal matching will be incident to a vertex in the $K_{k-1}$. Thus, the size of the maximal matching on this graph is $k-1$. This graph has $\left(\begin{array}{c}k-1 \ 2\end{array}\right)+(n-k+1)(k-1)$ edges, and it is the extremal graph.

E-mail: help-assignment@gmail.com  微信:shuxuejun

help-assignment™是一个服务全球中国留学生的专业代写公司