Skip to main content

All Questions

Filter by
Sorted by
Tagged with
27 votes
5 answers
6k views

The Matrix-Tree Theorem without the matrix

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me ...
8 votes
2 answers
693 views

Seeking a combinatorial proof for a binomial identity

Let $n\geq m\geq0$ be two integers. The below binomial identity is provable by other means: $$\sum_{j=0}^m(-1)^j\binom{n+1}j2^{m-j} =\sum_{j=0}^m(-1)^j\binom{n-m+j}j.$$ QUESTION. Can you provide a ...
2 votes
2 answers
1k views

Decomposition of $K_{10}$ in copies of the Petersen graph

It is a well-known and cute exercise in algebraic graph theory to show that $K_{10}$ cannot be written as the edge-disjoint union of three copies of the Petersen graph $P$. Indeed, the graph $G$ whose ...
12 votes
11 answers
2k views

Giving a math talk with no blackboard or projector

I need to give a math talk to a group of undergraduates. I am asking for advice because this talk will take place at a department picnic and there will be no blackboard or projector. I would like to ...