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 to use graph theory as a vehicle by which to convey a sense of developing "advanced" mathematics (remember, these students will have seen first-year calculus, at best).
What are you favorite interesting and accessible nuggets of graph theory?
"Interesting" could mean either the topic has a particularly useful application in the real-world or else is a surprising or elegant theoretical result. An added bonus would be if the topic can reveal gaps in our collective knowledge (for example, even small Ramsey numbers are still not known exactly). "Accessible" means that a bright, motivated student with no combinatorial background can follow the development of the topic from scratch, even if it takes several lectures.
 A: The "$-1$ colors" theorem. This allows you to talk about coloring, about chromatic polynomials, and (for example) about hyperplane arrangements, their chambers and so on (Orlik+Terao's book on hyperplane arrangements has the details) 
Doing everything in detail is a bit of work, but you probably don't need that.
Everyone with appreciation for beautiful math should fall for this!
A: Coloring problems are beautiful and accessible.  If you're mentioning Ramsey numbers (as you should!), it will be easy to segue into coloring problems (or vice versa).
Some topics worth including would be


*

*Bipartite iff 2-colorable

*Four/Five Color Theorems

*Chromatic number, basic bounds

*Edge chromatic number, Vizing's Theorem, König's Line Coloring Theorem


These were some of my favorite results in my first graph theory course.
A: Here is a topic that he kept me wasting (?) many hours: there is a theorem that every embedding in 3-space of $K_7$ , the complete graph on 7 vertices, contains a knot. Draw such an embedding and find the knot(s)! 
Every embedding of $K_6$ contains a link, but that is usually much easier to find. 
If I can find the reference, I'll add that as a comment. 
A: 1) As you say in the question, Ramsey numbers, both the (easy) upper bound - an elegant example of the power of combinatorics - and the lower bound, one of the rare proofs that is easy, short, and completely surpising.
2) Turan's theorem about the size of independent sets in graphs. Again, an easy application of the probabilistic method (though you don't even need the language of probability to state it). It's also interesting that this is an example, unlike Ramsey numbers, where the 'easy' proof actually gives the best possible bound (for general graphs).
Of course given the wide variety of problems graphs are applicable to, it's useful to be able to detect structured subgraphs, either complete graphs or independent sets. These are also good examples of non-constructive proofs.
A: I think that presenting the connection between random walks and electrical networks (like in the classic text "Random walks and electric networks" by Doyle and Snell) is an interesting  and feasible idea. Just a week ago I taught a 6-day course about this to talented high schoolers and it worked out very nicely. It's a good opportunity to show them interesting applications of probability and give a flavour of a vibrant field of mathematics. Plus, there is a quite a lot of room for digressions on Markov chains, spectral graph theory etc.
A: This is probably not what you're looking for, but if I were teaching such a course I'd focus on the interplay between algorithms for various graph problems and the more traditional mathematical approach of proving theorems in graph theory.  
For example, you can prove the "max flow-min cut" theorem by developing an algorithm that simultaneously finds a maximum flow and a corresponding min-cut.  
A: I have found that the Art Gallery Problem engages middle- and high-school students, and quickly leads to the unknown, which itself can be eye-opening to students. (On the latter point, students tend to think of mathematics as settled, so it is nice for them to reach unsolved problems they can comprehend, which abound at the interface between geometry and graph theory.)
Proving the traditional art gallery theorem (that $\lfloor n/3 \rfloor$ guards suffice and are sometimes necessary to cover an $n$-wall gallery) introduces triangulations and the chromatic number of a graph.  There are many sources, including the recent book (if I may self-promote) Discrete and Computational Geometry.
               


Addendum. May I also recommend "How to Guard an Art Gallery and Other Discrete Mathematical Adventures", by T.S. Michael, whom I had the pleasure of teaching two decades before his book was
published.
A: I think the graph isomorphism problem is a good choice: it's a fundamental question and a good lead in to the notion of isomorphic and some complexity theory---it's not known if it's NP-complete.  This should be doable in a couple of lectures, depending on how thorough you want to be.  
There are also applications, but I'm not the one to tell you about them.
A: Some very accessible and interesting content that I think would cause a positive impression can be found in the book "Graphs and their uses" by Oystein Ore. 
If I was to give an introductory course on graph theory for such an audience, I would follow part of this book at the beginning and then I would complement with something else. I would start with a classic problem: is it possible to connect through paths in the plane each one of three wells to each one of three different houses without intersections? There is a very neat and elementary explanation on why this is not possible that only uses the Jordan's curve theorem.
After mentioning other classic examples such as the Königsberg bridge problem (and the criterion to find eulerian paths in a graph) and hamiltonian cycles (stressing the lack of an efficient general method to find these), I would move to a remarkable fact that is sometimes known as the "sports journalist paradox", according to which is quite common to find, in some sports tournaments where each team plays against each other, an oriented cycle that involves all teams; in other words, team A wins team B, which wins team C, and so on...till some team in the chain wins team A! It is not difficult to characterize when we can find such a behaviour, and the answer turns out to be quite often!
I would then mention map coloring, and give a complete proof of the five color theorem. But most important, I would discuss Euler's formula for poligonal nets and how to apply it to characterize all platonic solids. This achievement, while elementary, could be a nice way to keep the audience interested and pave the way to further deeper results.
A: It seems to me that your goal should be to give them some elementary results with proofs (so they get used to that type of thinking) but also some high-level, cool, and surprising results to whet their appetite for more. In studying planarity you can find many cool and surprising results. I took a course from Laszlo Lovasz on such topics a few years ago, and he put his lecture notes online. You can link to them from this site: http://www.cs.elte.hu/~lovasz/geomgraph.html
Highlights I think high school students could understand and enjoy (perhaps skipping some of the proofs):


*

*Section 1.1. Kuratowski's Theorem: A graph $G$ is embeddable in the plane if and only if it does not contain a subgraph homeomorphic to the complete graph $K_5$ or the complete bipartite graph $K_{3,3}$.

*Section 1.3. Steinitz's Theorem: A simple graph is isomorphic to the skeleton of a 3-polytope if and only if it is 3-connected and planar.

*Section 2.1. Unit Distance Graphs

*Chapter 4. Turning the edges of $G$ into rubber-bands and talking about when they find equilibrium in the form of a planar representation of $G$


Finally, Chapter 6 has some really amazing results:


*

*The Cage Theorem: Every 3-connected planar graph is isomorphic to the 1-skeleton of a convex 3-polytope such that every edge of the polytope touches a given sphere.

*Koebe's Theorem: Let $G$ be a 3-connected planar graph. Then one can assign to each node $i$ a circle $C_i$ in the plane so that their interiors are disjoint, and two nodes are adjacent if and only if the corresponding circles are tangent.

A: Take a look at my graph theory site, http://mathcove.net/petersen and let me know if the Petersen program would be useful. I would be willing to grant you a free license.
Chris Mawata
A: How about graphic sequences? This might be a nice introduction to the world of inverse problems - an important concept of whose existence most high school curricula wouldn't even hint.
A: Matching theory. This includes Hall's marriage theorem, Tutte's theorem and the Gale-Sharpley stable matching theorem.
One reason to teach this subject to undergrads is that it changes the way mathematicians think about algorithms. The standard algorithms one learns in high school and undergraduate studies (Dijkstra algorithm, quicksort and the likes, etc.) are all generally looked down on by mathematicians, as they (1) seem to be just particularly efficient methods to compute some objects which are already clear to exist, (2) are usually of low complexity (much lower than that of proofs in undergraduate mathematics), (3) add no theoretical value (in fact they do, but algorithmic content in mathematical proofs is often cleverly hidden by whoever writes up the proof, so it looks like they don't). In contrast, the perfect matching algorithm (by using augmenting paths) and the Gale-Sharpley algorithm are rather nontrivial and actually are major components in the proofs of the existence of perfect matchings rsp. stable matchings.
A: Planar graph duality. E.g. the facts that


*

*A set of edges forms a connected spanning subgraph of a planar graph G if and only if the complementary set of edges forms an acyclic subgraph of the dual, and vice versa.

*Since spanning trees are just connected acyclic subgraphs, it follows that a subgraph is a tree if and only if its complement is dual to a tree. Euler's formula follows immediately.

*The edges that are not in the minimum spanning tree of a planar graph G are the duals of the edges that are in the maximum spanning tree of its dual.

*A planar graph is bipartite if and only if its dual is Eulerian.

*A planar graph is 3-connected (polyhedral) if and only if its dual is.

*The graphic matroid of a planar graph is the dual of the graphic matroid of the dual graph. Planar graphs are the only graphs for which the dual of the graphic matroid is also graphic.

*A directed planar graph is acyclic if and only if its dual graph (with the dual edges oriented 90 degrees clockwise from the primal ones) is strongly connected.

A: One problem that I found quite interesting is the Hadwiger-Nelson problem for coloring the plane. The proofs that the answer is at most $7$ and at least $4$ are easy and elegant (but also quite different), and it has the added bonus that it is an open problem.
Edit: The chromatic number is now known to be at least 5.
A: I'd suggest Turán's theorem, the bonus being the somehow surprising  hardness of the corresponding problem for 3-uniform hypergraphs. 
A: On the application side, you can introduce graph theory as a way to model connected systems: 


*

*web pages (familiar, has some nice visualizations, but hard to get your hands on),

*people a la Stanley Milgram and "six degrees of separation" (important but very "fuzzy"),

*actors connected by movies (precise via the Internet Movie Database and front-end Oracle of Bacon -- for ideas on using this, see my PRIMUS article "Kevin Bacon and Graph Theory," available through my web page)

A: I believe the book

Hajnal Péter: Gráfelmélet. 1997, Polygon, Szeged.  

is an extended answer to exactly this question.  (There's a second edition from 2003, but apparently no translations to other languages.)
The writing style of this book makes it accessible to high school students (as opposed to the Lovász book whose concise style makes it ideal for research mathematicians).  Thus, most of the material is accessible at high school level, while at the same time the book covers so many difficult topics that it'd be difficult to cover all the proofs even in a semester long high school course.  
The book remains a useful reference for BSc combinatorics exams (not alone though, because some necessary topics are missing).
Here are some of the topics included (many of these were mentioned in other responses).


*

*Flow-cut theorem and algorithm, Menger's theorems, Kőnig-Hall, maximal matching algorithm for bipartite graphs, Tutte's theorem, and even Edmond's algorithm to find maximal matching in any graph.  

*Euler circuits, then Dirac's sufficient condition for Hamiltonian circuit

*Graph coloring, Brooks' theorem (when a graph's chromatic number reaches its maximum degree), high chromatic graphs without triangle, Hajós's characterisation of graphs with chromatic number (exercise 9.16 in Lovász), Vizing's theorem on edge coloring, 

*Turán's theorem, Erdős-Stone theorem about the asymptotic on the number of edges of a graph not containing a particular non-bipartite graph, asymptotic for $ C_4 $-free graphs.

*Ramsey theorems.

*Complexity theory results about graph problems, including Karp reductions between Hamiltonian circuits and chromatic number and independence number.  Does not include the Cook-Levin theorem so no problem is actually proven to be NP-complete.

*Planar graphs, duality, Whitney-duals, Euler's theorem, Kuratowski's theorem on the characterization of planar graphs (yes, with a proof), Robertson and Seymour's graph minor theorem without proof, the four color theorem without proof, the five color theorem and Kempe's proof, Hadwiger's conjecture.

*Perfect graphs, Lovász's theorem on the complement of perfect graphs (yes, with a proof), comparability graphs of posets are perfect.


Note finally that before any topic, you'd need to cover some of the first chapter which introduces basic terminology about graphs, which is important to plan if you are giving only a few lectures.  (Have you told us about the total length of lectures you are planning to give?) Edit: ah, I see the lectures the question is referring to are now in the past, so there's no point to ask such a concrete question.
