Graphs and Subgraphs

2018 January 12

In modern mathematics, there are two major subfields, algebra and analysis, which Moor Xu helpfully describes as

<strong>Algebra</strong> is the study of collections of objects (sets,
groups, rings, fields, etc). In algebra, people care more about the
structures of these collections and how these collections interact than
about the objects themselves.
This is in direct contrast with <strong>analysis</strong>, which primarily
studies individual objects; for example, an analyst might study the
smoothness of an individual function.

I like both, but my courses right now center around analysis, so I've spent my winter break reading a few algebra texts, especially Graph Theory with Applications by Bondy & Murty.

If you're a younger undergrad who enjoys mathematics, I highly recommend going through the beginning, which is quite accessible. Here are some of my proofs for the exercises in Chapter 1: Graphs and Subgraphs. I provide background on definitions so that you don't have to know much about graph theory to understand my proofs. Because this blog is written for younger undergrads, I will emphasis intuition over rigour.

1.1 Graphs and Simple Graphs


This exercise is a pretty easy way to learn what a graph is.

A graph is a collection of vertices (points) and edges (lines) connecting those points. We denote a graph with a capital letter (e.g. G). We denote the set of its vertices V(G) and the set of its edges E(G). We use the Greek nu (ν) to denote the number of vertices in the graph, and we use the Greek epsilon (ϵ) to denote the number of edges. We say that a graph G is congruent to a graph H if every vertex in G can be mapped by a bijection to a vertix in H, and the same for every edge; we denote congruence with G ≅ H.

(a) Show that if G ≅ H, then ν(G)=ν(H) and ϵ(G)=ϵ(H)
(b) Give an example to show that the converse is false

My solution
(a) If G ≅ H, then every vertex in V(G) can be mapped with a bijection to a vertex in V(H) by the definition of graph congruence. Thus, the number of elements in V(G) is equal to the number of elements in V(H). It immediately follows that ν(G)=ν(H). The same argument applies for ϵ(G)=ϵ(H).

  1. Both G and H below have 4 vertices and 3 edges, but they are not congruent.
    <div id="graph-G" class="graph"></div>
    <div id="graph-H" class="graph"></div>