Graph Theory - Trees

This post is second in a series of compendium-style posts, intended as an encyclopaedic collection all of the useful properties of a certain class of objects relevant to one of my courses (in this case, graph theory). I realise that this posts are slightly unappealing to read, but they constitute excellent revision.

Today, I'm interested in trees.

Definition. The following give equivalent conditions for a graph $G$ to be a tree:

1. $G$ is connected and acyclic.
2. $G$ is minimally connected.
3. $G$ is maximally acyclic. 
4. $G$ is connected with $e(G)=n-1$.
5. $G$ is acyclic with $e(G)=n-1$.

At first, we start with the first definition. Equivalence of 1,2 and 3 are established via follow-your-nose contradiction arguments. Equivalence of 1, 4 and 5 will come later.

A (finite) graph is connected $\Leftrightarrow$ it contains a spanning tree.

A minimally connected subgraph of $G$ gives a spanning tree. Conversely, a spanning tree is obviously connected, and the supergraph of a connected graph is connected.

Every tree $T$ with $|T|\geq 2$ has at least two leaves.

A leaf is a vertex with exactly one neighbour.

Pick a vertex $x_1$. Consider a maximal path from $x_1$, say $x_1x_2\ldots x_k$. Let $y$ be a neighbour of $x_k$, $y \neq x_{k-1}$. If $y$ is in the path, we have found a cycle. If $y$ is not in the path, we can extend the path to $x_1x_2\ldots x_k y$, contradicting maximality. So $x_k$ is a leaf. 

Now, repeat this argument, starting from $x_k$, to find a second leaf. 

A tree $T$ of order $n$ has size $n-1$. 

We induct on $n$. The base cases $n=1,2$ are clear. Pick a leaf $v$. Then $T-v$ is connected, acyclic, hence a tree, and so $e(T-v)=n-2$ by the induction hypothesis. 

We can use this to prove equivalence of definitions 1,4 and 5, above. 

(Cayley's theorem) There are $n^{n-2}$ labelled trees of order $n$.

We construct a bijection between labelled trees and strings of length $n-2$ over an alphabet of $n$ letters. (The sequence corresponding to a tree is called its Prufer sequence.)

(Algorithm for tree $\rightarrow$ string)

• Select the lowest labelled leaf, record its neighbour, remove it. 
• Repeat previous step until exactly one edge is left, and stop.

This produces a string of length $n-2$ with values in $\{1,\ldots,n\}$.

(Algorithm for string $\rightarrow$ tree)

• Set all vertices to "unused". 
• Select the smallest "unused" vertex that does not appear in the string, mark it "used", and join it to the vertex labelled with the next value in the string. Delete this vertex from the string.
• Repeat previous step until the string ends.
• Finish off by connecting the last two unused vertices.

None of the steps produces a cycle (when we mark a vertex used, none of the branches "behind" it are ever touched again), and we create $n-1$ edges. Thus, by definition 5 above, we have a tree. 

$(4,4,4,4)$	$(4,6,4,5)$

Sanity check: note that each node appears in the sequence $d(v)-1$ times, where $d(v)$ is its degree.

These processes are inverse to each other, and so we have a bijection. There are $n^{n-2}$ possible strings, and so there are equally many possible labelled graphs. $\square$

Things to think about: Can we obtain a description of the number of isomorphism classes (unlabelled graphs) by thinking about the size of the orbit of $(a_1,a_2,\ldots,a_{n-2})$ under the action of $S_{n-2}$ on the set of Prufer sequences given by $(\sigma(a_1),\sigma(a_2),\ldots,\sigma(a_{n-2}))$, for $\sigma \in S_{n-2}$, or is it more complex than that?

Existence of spanning tree $\Leftrightarrow$ Zorn's lemma
Extracurricular result

Assuming Zorn's lemma, every (connected) graph has a spanning tree: consider the set of all subgraphs that are trees, ordered by inclusion. This is obviously chain-complete (the acyclic definition survives unions of chains), and a maximal element corresponds to a spanning tree.

[Proof of the converse omitted currently, as I want to try to come up with a proof myself at some point.]

Graph Theory - Planar graphs

Graph theory is first and foremost about combinatorics, and so graphs certainly could be thought of as abstract objects in their own right, much like groups, or vector spaces. However, their interpretation in terms of ("physical") vertices and edges is highly suggestive, and often provides us with motivation and/or a foothold for an intuitive understanding of the underlying objects.

One (combinatorial) property of graphs that would be almost impossible to dream up without this visualisation is planarity. (A graph is said to be planar if it can be embedded in the Euclidean plane without any of its edges crossing. Thus, in some sense, any planar graph corresponds to a polygonisation of the plane.¹) We can push this topologically motivated program further by defining other flavours of planarity, embedding graphs on various topological surfaces, such as the torus, or the Klein bottle. It's fascinating to take a moment to observe that, in doing so, we are forging a link between topology and combinatorics, two wildly different fields of study. The link closely involves the Euler characteristic of the surface, as we will show in a moment, and raises the question: is the Euler characteristic a topological constant, or a combinatorial one?

This post will contain a collection of results and comments concerning planar graphs. I intend to update it as I work through my notes.

Note that we need at least 3 vertices for planar graphs to become non-trivial.

A maximal planar graph corresponds to a triangulation.

This is a crucial observation. If you have any face of size (number of edges) greater than 4, you can draw in a diagonal to obtain a new graph $G^\prime$ containing $G$. Furthermore, a maximal planar graph is bridgeless, and connected. You can extend any finite planar graph to a maximal planar graph.

There are actually only two non-planar graphs (in the plane).

Every time that a graph fails to be planar, the problem can be traced back to one of two generic cases. There are only two geometric "obstacles" to planarity!


It's fairly obvious that any graph containing a non-planar subgraph can't be planar. We need to extend this concept slightly to "subdivisions". We obtain a subdivision of a graph by replacing one edge with a path of edges spanning several vertices. It's easy to see that any graph containing a subdivision of a non-planar graph can't be planar.

Two simple non-planar graphs are shown above: $K_{3,3}$ and $K_5$. From the above observations, it's immediate that any graph containing a subdivision of $K_{3,3}$ or $K_5$ is necessarily non-planar. The amazing fact is that the converse is also true, by Kuratowski's theorem: $G$ is non-planar $\Leftrightarrow$ $G$ contains a subdivision of $K_5$ or $K_{3,3}$. The proof of Kuratowski's theorem is not included in the course.

Note: To see that $K_5$, and $K_{3,3}$ are indeed non-planar, you can check that they both violate the bound on the edges in terms of the girth given below. You can also argue constructively by drawing them in a methodic fashion.

Euler's formula.

Let $G$ be a connected planar graph with $n$ vertices, $m$ edges, and $f$ faces. Consider any surface of Euler characteristic $E$. Then the following formula holds:

$$n-m+f=E$$

We give a proof for the case $E=2$, corresponding to the Euclidean plane.
Proof: We induct on $m$, for fixed $n$.
$G$ is connected, so contains a spanning tree, which has $n-1$ edges, so $m \geq n-1$.

• If $m=n-1$, then $G$ is equal to its spanning tree, so there is only one face (a tree is acyclic). Thus $n-m+f=n-(n-1)+1=2$, as required.
• If $m>n-1$, then $G$ must contain a cycle. Pick an edge $e$ of any cycle. Then $e$ separates two distinct faces. Also, $G-e$ clearly remains connected. By the induction hypothesis applied to $G-e$, $n-(m-1)+(f-1)=2$, which directly implies the required result for $G$. $\square$

Note: Euler's formula proves that the number of faces of a planar graph is independent of the way that you choose to realise its embedding in the plane (the sizes of the different faces are not!)

There are strong restrictions on the number of edges a planar graph can have.

Let $G$ be a planar graph with $n\geq 3$ vertices, and $m$ edges. Then $m \leq 3n - 6$. This is easy to prove, as when $G$ is a triangulation $2m=3f$, and the result with equality pops right out of Euler's formula (and every planar graph can be extended to a triangulation simply by adding edges).

We can be more precise by obtaining bounds on the number of edges in terms of the girth $g$ (length of the shortest cycle in the graph). Assume G is connected. If G is acyclic (a tree) the number of edges is less than the number of vertices, so assume the graph has a cycle, so that the girth $g\geq3$ is defined. Observe that $2m = \sum i f_i$, where $f_i$ is the number of faces bordered by $i$ edges. (If some face borders both sides of the same edge, we should count that edge twice.) This gives: $2m = \sum i f_i \geq gf$, allowing us to conclude that $m \leq \displaystyle \frac{g}{g-2}(n-2)$ from Euler's formula. Note that substituting $g=3$ recovers the special case obtained above by considering triangulations.

This is a remarkably strong restriction, as in general a graph can have up to $n \choose 2$ $\sim n^2$ edges. So, in some sense, most graphs contain a substructure isomorphic to either $K_{3,3}$ or $K_5$. Maybe we can conceptually draw a link to Ramsey theory here?

There is one more piece of information left to squeeze out of the above, but at this point it's hardly surprising. The minimum degree $\delta(G)$ of a graph is closely linked to the number of edges, so we can easily obtain a (strong) upper bound as a corollary. If $\delta(G) \geq 6$, then $2m \geq 6n$ by the handshaking lemma, contradicting $m \leq3n - 6$ (recall $n\geq 3$). We conclude that planar graphs must satisfy $\delta(G)\leq 5$.

---

1 This may get tricky for infinite/uncountable graphs. Something interesting to think about! See my relevant stackexchange post, which has generated a decent amount of interest.

Linear Analysis - Riesz's lemma

In Linear Analysis, during the chapter discussing finite-dimensional normed spaces, we proved Riesz's lemma:

Let $Y$ be a proper, closed subspace of a normed space $X$. Then $\forall \varepsilon > 0$, $\exists x \in X$, $\|x\|=1$, such that $d(x,Y) > 1 - \varepsilon$.

I find the proof very interesting.

In school, we learn Pythagorus' theorem in all of its (potentially tautological) majesty. From that moment onwards, the name Pythagorus is endowed with a reverent, mystical quality that we revere because as small, impressionable children we were taught to. In France, there's another name that is given equal attention that as far as I know is less widespread in the UK - Thales (of Miletus). Apparently, he used the properties of similar triangles to calculate the height of the pyramids (although I've also heard said that this is another instance of misplaced mathematical credit, and he had nothing to do with the pyramids). Anyway, besides Pythagorus, we are patiently force-fed the théorème de Thalès, i.e. that the ratios of the sides of similar triangles are equal (image courtesy of Wiki)

Going through the proof of Riesz's theorem, it strikes me as very similar to this basic theorem of Euclidean geometry.

Proof of Riesz's lemma:

• We assumed $Y$ proper, so pick $z \in X\backslash Y$. 
• We assumed $Y$ closed, so $d(z,Y)=\inf\{\|x-y\| \mid y \in Y\} > 0$. By definition of infimum, we can pick $y \in Y$ such that $d(z, y)(1 - \varepsilon) < d(z,Y)$.
• Set $x = \displaystyle \frac{z-y}{\|z-y\|}$. Thus $\|x\|=1$. This is the point that we are looking for.
• Write $\lambda =\displaystyle \frac{1}{\|z-y\|}$ for clarity. $d(x,Y)=d(\lambda (z-y), Y) = \inf\{ \| \lambda (z - y) - y^\prime\| \mid y^\prime \in Y\}$. 
• Using the fact that subspaces are closed under scalar multiplication, $d(x,Y) = \inf \{\lambda \| (z-y) - y^\prime \| \mid y^\prime \in Y \}$.
• Using the fact that subspaces are closed under vector addition, $d(x,Y) = \inf\{\lambda\| z - y^\prime \| \mid y^\prime \in Y\}$.
• We conclude that $d(x,Y)=\lambda d(z,Y) > 1 - \varepsilon$, by choice of $y$. $\square$

(Perceived) link with similar triangles

I'm interested in one specific step of the proof: the assertion that for $Y$ a closed vector subspace, $d(\lambda x, Y) = \lambda d(x,Y)$, for $\lambda \in \mathbb{R}$.

 

Look familiar? The above argument with the infimum holds for any subspace. But how analagous is it really? There are a few traps for our intuition here. We haven't assumed that $X$ is a Hilbert space, so we can't assume that the shortest distance from $x$ to $Y$ is along a perpendicular line. That's fine - similar triangles don't have to be right-angled. More subtly, for the shortest distance to be along a line, we're assuming that lines are geodesics in normed spaces. Apparently, they are, but apparently there can be other geodesics too. 

I was sort of hoping we might be able to argue that the similar triangles property holds in this case without using the analytic definition of $d(x,Y)$, but the potential non-uniqueness of geodesics messes that up. There are other complications - recall that there may be multiple closest points in $Y$, since $X$ is not a Hilbert space, and we don't yet have any reason to believe that the closest points to $x$ and $\lambda x$ respectively are colinear in $Y$. Thus it seems that studying this question is out of my reach at the moment (my knowledge of geometry and geodesics is currently rather sketchy).

Normed spaces are sort of paradoxical - it feels to us like they have an extremely nice, rigid structure, yet things can apparently fail in mysterious ways. I certainly catch myself thinking of them intuitively as if they necessarily admitted an inner product (and thus had an orthonormal basis). This section is unfortunately rather inconclusive. 

Important corollary of Riesz's lemma

The unit ball of any infinite dimensional normed space is not compact.

Related problem: Example sheet 1Q12

Show that in the unit ball of every infinite-dimensional normed space, there is a sequence $(x_n)$ with $\|x_n - x_m \| \geq 1$, $\forall n \neq m$. Can $\geq$ be replaced with $>$?

In finite dimensions the unit ball is compact. If Riesz's lemma works for any $\varepsilon > 0$, then it has to work for $\varepsilon = 0$ by compactness. This approach might have been very interesting in infinite-dimensional normed spaces with compact unit balls. However, Riesz's lemma shoots itself in the foot by preventing any such objects from existing. Damn.

 Can $\geq$ be replaced with $>$?

Yes. Our supervisor came up with a proof that doesn't use Hahn-Banach. [more details to come]

Hi. Welcome to my blog. The idea behind this is some sort of revision diary. Of course, ideas mature and morph over time. I'm interested to see how this turns out.

I'm currently doing Part II of the Maths Tripos at Cambridge. It's hard - but I think I'm making it harder than it needs to be. I've been approaching things from the wrong perspective so far, working in the wrong way. The Cambridge Tripos is about Maths. In order to be successful, all you need to do it be legitimately interested in Maths. Not even passionate - just interested, and actively curious. You need to get your hands on things, feel them out, mould them with your own hands. Read things, talk with people, exchange ideas. Get things wrong. Being a genius is not necessary (although I'm told it helps).

I have this half-baked theory that the best way to learn Mathematics is through communication. I guess we'll find out.