Solving graph theory proofs

Question

I am trying to study for an exam on graph theory and I have a few questions. How would you start a proof? For example, when I see a problem like this:

Let G be a graph with n vertices where every vertex has degree at least n/2. Prove that G is connected.

How would I start this off? I know how to solve this now but for problems like that, how would I start the question? And for things like, prove that a graph has a bridge, etc. Like, how do I know what to start looking for when I see a problem like that?

Answer 1

I realised how old this post is after I had written my answer but figured I would post anyway since the question has been viewed many times and hopefully my answer will be helpful to others. For the record, I am about to start a PhD in graph theory.

Practice, practice, practice. This will help you to become more familiar with which proof methods tend to work well for which kinds of problems (as in other areas of maths, often there is more than one possible method, some of which will reach the answer more quickly than others). Look at examples, practice questions.

• My graph theory lecturer often advised us to start by considering "small examples" and look for a pattern. In your example, draw/think about some graphs with small numbers of vertices. What can we say about such graphs and does that help us make a general statement about them (i.e. why must they be connected)?
• Another good method for proving some statements in graph theory is proof by contradiction. I often find this to be a good method to try first (and is what I used to prove your statement) since it requires me to think more about exactly what the statement is saying i.e. what does it mean for a graph to be connected?
• Other methods include proof by induction (use this with care), pigeonhole principle, division into cases, proving the contrapositive and various other proof methods used in other areas of maths.

Another possibly obvious but important starting point is to spend a moment thinking about the definitions used in the statement. In your example, start by thinking carefully about what it means for a graph to be connected and what will a graph where every vertex has degree $n/2$ look like? I will now run through my thought process in proving the given statement by contradiction.

Suppose for a contradiction that $G$ is not connected. What does this mean? It means that there is some vertex $v$ which cannot be reached (via a path) from some vertex $u$. What does that mean (try to picture the situation)? It means that any vertex $w$ which is adjacent to $u$ also cannot reach $v$ (otherwise we could join the edge from $u$ to $w$ to the path from $w$ to $v$ to form a path from $u$ to $v$). In fact, any vertex which can be reached from $u$ cannot reach $v$. Similarly, any vertex which can be reached from $v$ cannot reach $u$.

Denote those vertices in $G$ which can be reached from $u$ by $U$ and denote those vertices in $G$ which can be reached from $v$ by $V$. None of the vertices in $U$ can be adjacent to any vertices in $V$. Since every vertex in $G$ has degree at least $n/2$, every vertex in $U$ must be adjacent to at least half of the vertices in $G$. Similarly, every vertex in $V$ must be adjacent to at least half of the vertices in $G$. Since $U$ and $V$ each contain at most $n/2$ vertices, this is not possible: we have a contradiction.

The above is an extreme example and some will disagree, but I believe a few extra words and explanation can make a proof much clearer than symbols alone.

Answer 2

Philosophically speaking, if you don't know where to start a good idea is to try a proof by contradiction. In graph theory, this will usually give you some structure to latch onto, stare at, and hopefully reach a eureka moment.

For example, here is a proof of your problem by contradiction.

Proof. Suppose not. Then $G$ is disconnected. In this case we get to stare at the connected components of $G$. Now another useful principle is to look at the biggest or smallest structure (defined in a suitable sense). In this case, it is fruitful to look at the smallest connected component $G_1$ of $G$ (where smallest here means the fewest number of vertices). Thus, $G_1$ has at most $n/2$ vertices. But now, no vertex in $G_1$ can have degree at least $n/2$, which is a contradiction.

Answer 3

I will add some tips that I think are helpful when solving graph theory proofs, especially on exams.

• Bring a big eraser to exams, as proof writing (especially in graph theory, I have found), involves a lot of trial and error.

• First, try a few examples in which the theorem holds and try to think of counterexamples. Make sure you truly understand what the theorem is stating. Take note of why a proposed counterexample is not actually a counterexample. Often times trying to prove something involves dancing between proposed counterexamples and reasons why they are not counterexamples. Take note of patterns.

• Suppose not (work toward a contradiction).

• Consider the contrapositive.

• If you are thinking about trying induction, first think about what element (what vertex, if you are inducting on vertices) you will remove from the k+1 graph to get to a valid k graph. Then think about how you will apply the IH and work forward to the k+1 graph to complete the inductive step. Don't start writing the structure of the inductive proof until you have thought about these two steps and have an idea about how they will work. The base case is usually trivial.

• Look at biggest or smallest structures, as suggested above (you can always prove the existence of a smallest element, if the set of sizes are a nonempty subset of $\mathbb{N}$ [by WOP], and a maximal element, if the set of sizes are a finite nonempty subset of $\mathbb{N}$). These structures could be paths, cycles, connected components, etc.

• Division into cases

• As mentioned above, pigeonhole principle (what are the pigeons and what are the holes?), generalized PHP, handshaking lemma, |V|=|E|-|CC|, consider cycles (or lack thereof), connectivity (or lack thereof), etc. Generally, know as many theorems as possible... the more you know, the more tools you will have to solve a problem.

• Consider the complement of the graph you are working on.

• If your theorem says something about "every vertex" or "every edge" or "every connected component," think about one of those elements and what must be true about them

• Try to simplify your graph (like reducing the strongly connected components of a digraph into vertices, or reducing structures like cycles into vertices if you wanted to prove something about cycle adjacency, for instance)

Practicing is the best way to get better at this kind of thing.

Answer 4

I Googled "graph theory proofs", hoping to get better at doing graph theory proofs, and saw this question. Here was the answer I came up with:

Suppose G has m connected components. A vertex in any of those components has at least n/2 neighbors. Each component, therefore, needs at least (n/2 + 1) vertices. Thus, in the whole graph there are m*(n/2 + 1) vertices. When m is greater than 1, that is bigger than n, so m can only be 1. Having only 1 connected component, G is connected.