3
votes
2answers
526 views

Neat results from algebraic graph theory

Studying algebraic graph theory, I've stumbled across a wide range of results that I found pretty stunning and also useful. I'd like to share them here and ask for your favorite result from this area? ...
10
votes
3answers
952 views

Proofs of parity results via the Handshaking lemma

I particularly like the following strategy to prove that the number of some combinatorial objects is even: to construct a graph, in which they correspond to vertices of odd degree (=valency). Let me ...
23
votes
18answers
6k views

Interesting and Accessible Topics in Graph Theory

This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope ...
9
votes
3answers
852 views

Easier induction proofs by changing the parameter

When performing induction on say a graph $G=(V,E)$, one has many choices for the induction parameter (e.g. $|V|, |E|$, or $|V|+|E|$). Often, it does not matter what choice one makes because the proof ...
3
votes
3answers
757 views

Is there a bipartite analog of graph theory?

I would like to compile a list of questions about graphs that have a non-trivial analogs for bipartite graphs. Let me give the following examples: Cycle vs Even cycle. Most questions about cycles ...
8
votes
11answers
13k views
29
votes
20answers
3k views

Generalizations of Planar Graphs

This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...