Hot answers tagged

3

This is not possible. As is commonly a good approach, let us suppose that the least number of primary points anyone gets is $m$ and the most is $M$. We have that someone who earned $m$ primary points can earn no more than $mM$ total points, which occurs if they beat only players with $M$ primary points. Conversely, someone who earned $M$ primary points can ...


3

Everything looks good except for when $p$ is odd, the part where you say it has at most $MN$ edges if the parts have sizes $M$ and $N$ is very good. I would proceed as follows: Clearly $M+N=p$ so we can assume $M\geq N$ and $M=\frac{p+k}{2}$ and $N=\frac{p-k}{2}$, for some positive integer $k$. The options for $k$ are $0,2,\dots,p$ if $p$ is even and $1,3,...


3

As already noted in comments: $\alpha$ and $\beta$ are explicitly specified to be "one-to-one correspondences", which is a way of saying "bijections". Since there is a bijection between $V_G$ and $V_H$, they have the same number of elements. Similarly, since there is a bijection between $E_G$ and $E_H$, they have the same number of elements.


2

Yes. If it has no directed cycles, you can sort it topologically. However, because this is a tournament (i.e. there is an edge between every pair of vertices), then this has to be a total (strict) linear order, which is isomorphic to the one you asked about. I hope this helps $\ddot\smile$


2

HINT: If you remove the edge $\{1,2\}$ from such a tree, you get a pair of trees, the subtrees rooted at $1$ and at $2$; call these $T_1$ and $T_2$. You can split the remaining three vertices, $3,4$, and $5$, arbitrarily between $T_1$ and $T_2$. For $k=0,1,2,3$, how many ways are there to assign $k$ of these three vertices to $T_1$ (and the rest to $T_2$)? ...


1

The proof is by a form of induction, namely maximal counterexample. Let $S$ denote the set of all graphs on $n$ vertices, that violate the theorem. If $S$ is empty, we are happy as the theorem is true. If $S$ is nonempty, it must be finite, as there are only finitely many graphs on $n$ vertices. Hence, if we consider the ordering on $S$ based on number ...


1

Recall that $$\chi(t)=\det(tI-L)=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{k=1}^n\left(t[k=\sigma(k)]-L_{k,\sigma(k)}\right)\;,\tag{1}$$ where $[k=\sigma(k)]$ is an Iverson bracket, equal to $1$ if $k=\sigma(k)$ and to $0$ otherwise. The terms in the summation on the righthand side of $(1)$ that contribute to the $t$ term in the polynomial $\chi(...


1

I want to disagree with the answer by Newb slightly, but mainly just to point out some issues with formalism. Also if you answered $O(|V+E|)$ on my test you would get zero points and I'm sure there are other teachers like that. Since $V$ and $E$ are sets (exactly what kind depends on your particular definition of graph but the most prevalent definition in ...


1

I think you're describing a graded poset and you can use the term "graded graph". Eric's condition is correct and the homomorphism is usually denoted $\rho: V \rightarrow \mathbb{Z}$ where $(x,y) \in E \implies \rho(y) = \rho(x) + 1$ $\rho$ is called a rank function and is sometimes written $|x|$.


1

To give an idea of the difficulty of this problem here is the case of $d=2,$ which means we have a multiset of cycles. As there is just one cycle on $n$ nodes and the smallest cycle is a triangle these have generating function $$C(z) = \frac{z^3}{1-z}.$$ We get for the set of non-isomorphic $2$-regular graphs the generating function (Polya ...


1

I'm not sure you need to use removal lemma to prove your claim, you can prove it using simple combinatoric argument: every edge in the graph can participate, at most, in $n-2$ triangles. so, removing any edge will reduce the number of triangles in the graph by at most $n-2$ triangles. If you remove $\epsilon n^2$ edges, it will reduce the number of ...


1

Take a vertex with three edges. Assume you do NOT start there. Then there is a first time you will reach this vertex, through one of the possible paths leading to it. It won’t be the end of your drawing because two other paths are not yet traversed. Thus, you will leave this vertex, through a second adjacent path. As a result, when you traverse the third ...



Only top voted, non community-wiki answers of a minimum length are eligible