Skip to main content

Section 1.3 Basic Properties

We will now consider some basic properties of graphs and what we can learn about them.

Subsection 1.3.1 Degree and Neighborhood

First, a little useful vocabulary. If two vertices belong to an edge (i.e., there is an edge between them), we say they are adjacent . Two edges are adjacent provided they share a vertex (we can write this \(e_1 \cap e_2 \ne \emptyset\)).

If an edge “comes out of” a vertex (that is, if the vertex is an element of the edge) we say that vertex and edge are incident.

We will call the number of edges incident to a vertex its degree (or valency) and write \(d(v)\text{.}\) Because of our definition of a graph, \(d(v)\) is also the number of vertices adjacent to \(v\text{.}\)

We would like to refer to those vertices adjacent to a given vertex. We will call this set of vertices the neighborhood of \(v\text{,}\) and write \(N(v)\text{.}\) If we wish to include \(v\) as well, we could define the closed neighborhood and write \(N[v]\text{.}\) We will also sometimes consider the open or closed neighborhoods of sets of vertices \(A\text{,}\) and write \(N(A)\) or \(N[A]\text{.}\)

[Do we need more formal definitions of neighborhood, or just some examples?]

Note there is a connection between the degree of a vertex and its neighborhood: \(d(v) = |N(v)|\text{.}\) [Does this need more justification?]

Looking at the graph as a whole, we will let \(\delta(G)\) denote the minimum degree of \(G\) and \(\Delta(G)\) denote the maximum degree of \(G\).

We might also like to discuss that average degree of \(G\), which we will write \(d(G)\text{.}\) Compare this to the quantity \(\varepsilon(G) = |E|/|V|\text{.}\)

Activity 9.

How are the quantities \(d(G)\) and \(\varepsilon(G)\) related?

Solution

Note that the average degree of \(G\) as the sum of the degrees of each vertex of \(G\) divided by the number of vertices; that is, \(d(g)=\frac{1}{|V|}\sum_{v_{i}\in V} d(v_{i})\text{.}\) But \(\sum_{v_{i}\in V} d(v_{i})=2|E|\text{;}\) that is, the sum of the degrees of the vertices of \(G\) is twice the number of edges of \(G\text{.}\) Then we have \(d(g)=\frac{1}{|V|}*2|E|=2*\varepsilon(G)\text{.}\)

The previous activity suggests a proof for our first proposition about graphs.

Let \(G=(V, E)\) be an arbitrary graph where \(V_e \subseteq V\) is the set of vertices with even degree and \(V_o \subseteq V\) is the set of vertices with odd degree. Then \(\sum_{v \in V} d(v) = \sum_{v \in V_e} d(v) + \sum_{v \in V_o} d(v)\text{.}\) Notice that \(\sum_{v \in V_e} d(v)\) is even because each vertex in \(V_e\) is even and the sum of a collection of even numbers is itself even. We know that \(\sum_{v \in V} d(v) \) is even because \(\sum_{v \in V} d(v) = 2|E| \text{.}\) Each edge is incident to exactly 2 vertices, so each edge contributes 2 two the sum of degrees of the vertices. These 2 facts require \(\sum_{v \in V_o} d(v) \) to also be even because if \(a+b\) is even and \(a\) or \(b\) is known to be even, the other must also be even. Finally, each vertex in \(V_o \) has odd degree, so in order for the the sum of the degrees of all vertices in \(V_o \) to be even \(|V_o|\) must be even. Thus proving the claim.

Here is a much more challenging proposition. We should also try to figure out what it even means (morally). [What does the proposition tell us about graphs?]

Consider a graph \(G\text{,}\) if \(\delta(G) \gt \varepsilon(G)\) then the subgraph of \(G\) that is equivalent to \(G\) is the subgraph that we can call \(H\)

If \(\delta(G) \leq \varepsilon(G)\text{,}\) then we want to increase the minimal degree of the graph by removing one vertex of minimal degree.

We know that \(\delta(G) \lt \frac{|E|}{|V|}\text{,}\) and we want to show that removing a vertex with \(d(v_1) \lt \frac{|E|}{|V|}\) wont cause \(\frac{|E_{new}|}{|V_{new}|}\) to decrease to be less than \(\varepsilon(G)\text{.}\)

We know \(\frac{|E_{new}|}{|V_{new}|}=\frac{|E|-l}{|V|-1}\) where \(l\) is the number of edges removed by removing \(v_1\) so for \(l \lt \frac{|E|}{|V|}\) we have

\(l \lt \frac{|E|}{|V|}\)

\(-l > |E|+\frac{|E|}{|V|}-|E|\)

\(|E|-l > |E|(1-\frac{1}{|V|})\)

\(|E|-l > \frac{|E|(|V|-1)}{|V|}\)

\(\frac{|E|-l}{|V|-1} > \frac{|E|}{|V|}\)

Thus, so long as \(l \lt \frac{|E|}{|V|}\) we know that since \(l=\delta(G)\text{,}\) removing \(v_1\) from \(G\) will maintain that \(\varepsilon(G_{new})=\frac{|E|-l}{|V|-1} \gt \frac{|E|}{|V|}=\varepsilon(G)\text{,}\) maintaining the right hand side of our inequality.

So we remove \(v_1\text{,}\) then if \(\delta(G_{new}) \gt \varepsilon(G)\) let \(G_{new}=H\) if not, repeat this process of removing vertices of minimal degree.

Now we need to show that by repeating the above process we won't end up with the trivial graph. (by contradiction) if we did end up with the trivial graph, we know that \(\varepsilon(G_{new})=0 \lt \varepsilon(G)\) by definition. but this is a contradiction since we know removing vertices of minimal degree in the case that \(\delta(G_{new}) \leq \varepsilon(G)\) will never result in this being true. Thus the process must end before reaching the trivial graph.

Therefore, for every graph \(G\) with at least one edge, there is a subgraph \(H\) with \(\delta(H) \gt \varepsilon(H) \geq \varepsilon(G)\)

Subsection 1.3.2 Paths and Cycles

Definition 1.3.3.

A path is a a sequence of distinct vertices \(v_0, v_1, ..., v_k\) with edges \(v_i v_{i +1}\) for \(0 \leq i \lt k \)

The length of a path is \(k\text{,}\) or the number of edges.

Definition 1.3.4.

A cycle is a sequence of distinct vertices \(v_0, v_1, ..., v_{k-1}\) with edges \(v_i v_{i+1}\) for \(0 \leq i \lt k-1\) and edge \(v_0 v_{k-1}\text{.}\)

The length of a cycle is \(k\text{,}\) or the number of edges.

Activity 10.

How does the minimum degree of a graph relate to the length of its longest path and cycle?

Consider a longest path in \(G\) whose verticies I will denote \(v_0, v_1, ... ,v_k\text{.}\) Every neighbor of \(v_k\) must be part of the path becuase if it wasn't we could extend the path. Since all of the neighbors of \(v_k\) are on the path the degree of \(v_k\) cannot be more than the length of the path. Also since \(x_k\) is part of the graph it's degree cannot be less than the minumum degree of the graph. That is \(k \ge d(v_k) \ge \delta (G)\text{.}\)

If \(\delta (G) \ge 2\) then \(v_k\) will connect to \(v_{k-1}\) and at least one other vertiex in the path, making a cycle. Let \(v_i\) by the first vertex in the path that is adjacent to \(v_k\text{.}\) Then \(i \le k - \delta(G) \le k - d(v_k)\text{.}\) So \(v_i,v_{i+1}, ... v_{i-0=k},v_i\) is a cycle with length of \(i +1 \ge \delta(G)+1\text{.}\)

Paths are very useful. They allow use to define the distance between a pair of vertices, which in turn lets us define the diameter of a graph, central vertices and the radius of a graph. [Define these!]

Paths also give us a way to say what it means for a graph to be connected.

Cycles, on the other hand, lead to the definition of circumference as the length of a longest cycle in the graph, and girth as the length of a shortest cycle in the graph. We write \(\diam(G)\) for the diameter of \(G\) and \(g(G)\) for the girth of \(G\text{.}\)

Activity 11.

If a graph contains a cycle, what is the relationship between \(\diam(G)\) and \(g(G)\text{?}\) Be as specific as possible.

Let \(G\) be a graph, and let \(C\) be a shortest cycle in \(G\text{.}\) Assume, for the sake of contradiction, that \(g(G)\geq 2diam(G)+2\text{.}\)

Then \(g(C)=g(G)\geq 2diam(G)+2\text{.}\) Then \(C\) has two vertices whose distance from each other in \(C\) is at least \(diam(G)+1\text{.}\) However in \(G\text{,}\) these vertices have a lesser distance between them since there distance in \(C\) is at least \(diam(G)+1\) but their distance in \(G\) is at most \(diam(G)\text{.}\) Then any shortest path \(P\) between these vertices in \(G\) cannot be a subgraph of \(C\text{.}\)

But then we may use this shortest path to construct a new cycle including these vertices whose length is shorter than that of \(C\text{.}\) But then \(C\) is not a shortest cycle in \(G\text{,}\) a contradiction.