Graph Theory part 2

Let \( G \) be a simple graph with \( n \) vertices. We aim to show that \( m \leq \frac{n(n-1)}{2} \) and determine when equality holds.

In a simple graph, each edge connects two distinct vertices. The maximum number of edges a graph can have occurs when every pair of vertices is connected by an edge. In a simple graph with \( n \) vertices, the number of ways to choose 2 distinct vertices (which corresponds to the number of edges) is given by \( \binom{n}{2} \), which is the binomial coefficient for combinations.

The binomial coefficient \( \binom{n}{2} \) represents the number of ways to choose 2 elements from a set of \( n \) elements, and it can be expressed as:

This is the maximum number of edges a simple graph with \( n \) vertices can have.

Now, let's express the number of edges \( m \) in terms of the sum of the degrees of the vertices:

For a simple graph, the degree of a vertex is the number of edges incident to it. Since each edge contributes to the degree of two vertices, the sum of all degrees is twice the number of edges:

Using the Handshaking Lemma, which states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges, we have:

Simplifying, we get:

The maximum possible degree of a vertex in a simple graph is \( n-1 \) (when it is connected to all other vertices). Substituting this into our equation, we get:

Finally, we divide both sides by 2 to account for the double-counting of edges:

This proves that in a simple graph with \( n \) vertices, the number of edges \( m \) is always less than or equal to \( \frac{n(n-1)}{2} \), and equality holds when each vertex is connected to every other vertex.

Bipartite Graphs

a) Show that \(m \leq rs\):

In a bipartite graph \(G[X, Y]\) where \(|X| = r\) and \(|Y| = s\), each edge connects a vertex from \(X\) to a vertex in \(Y\). Therefore, the maximum number of edges (\(m\)) is achieved when every vertex in \(X\) is connected to every vertex in \(Y\). Hence, \(m \leq rs\).

b) Deduce that \(m \leq \frac{n^2}{4}\):

For a bipartite graph, the total number of vertices (\(n\)) is the sum of the sizes of the two partitions, i.e., \(n = r + s\). Substituting this into the previous result:

c) Describe the simple bipartite graphs \(G\) for which equality holds in (b):

Equality holds when each vertex in \(X\) is connected to every vertex in \(Y\), forming a complete bipartite graph \(K_{r, s}\).

Bipartiteness of Paths and Cycles

a) Every path is bipartite:

In a path, all vertices are connected linearly. Since each vertex is only adjacent to its neighboring vertices, a path can be easily divided into two sets, where vertices in one set are connected only to vertices in the other set. Thus, every path is bipartite.

b) A cycle is bipartite if and only if its length is even:

For a cycle, if the length is even, the vertices can be alternately colored in two sets, making it bipartite. However, if the length is odd, it is not possible to alternate colors without violating the bipartite property.

Vertex Degrees

For any graph \(G\), the minimum degree (\(δ(G)\)) is less than or equal to the average degree (\(d(G)\)), which is less than or equal to the maximum degree (\(∆(G)\)).

This inequality holds because the average degree is the total degree sum divided by the number of vertices. The minimum and maximum degrees set bounds on this average.

Bipartite Graph Properties

a) Show that \( \sum_{v \in X} d(v) = \sum_{v \in Y} d(v) \):

In a bipartite graph \( G[X, Y] \), the degree of a vertex is the number of edges incident to it. Every edge connects a vertex from \( X \) to a vertex in \( Y \). Therefore, the sum of degrees in \( X \) is equal to the sum of degrees in \( Y \).

b) Deduce that if \( G \) is \( k \)-regular, with \( k \geq 1 \), then \( |X| = |Y| \):

If \( G \) is \( k \)-regular, every vertex in \( X \) has degree \( k \), and every vertex in \( Y \) also has degree \( k \) due to the bipartite property. From part (a), the sum of degrees in \( X \) is equal to the sum of degrees in \( Y \). Since each vertex in \( X \) contributes \( k \) to the sum, and the same holds for \( Y \), the total number of vertices in \( X \) must be equal to the total number of vertices in \( Y \).

Problem: k-Partite Graph

Show that \( m \leq \frac{1}{2} \sum_{i=1}^k a_i(n - a_i) \), where G is a simple k-partite graph with parts of sizes \( a_1, a_2, ..., a_k \).

Solution:

Let \( G[X_1, X_2, ..., X_k] \) be a simple k-partite graph where \( |X_i| = a_i \) for \( 1 \leq i \leq k \).

The number of edges in G, denoted as \( m \), is given by:

Now, we can express \( m \) in terms of the sizes of the parts:

Expanding this sum gives:

Simplifying further:

Now, let \( n \) be the total number of vertices, i.e., \( n = \sum_{i=1}^k a_i \). Substituting this into the equation:

Finally, we get the desired inequality:

Problem: Diagonal Entries of A^2 and MM^t

For a simple graph \( G \), show that the diagonal entries of both \( A^2 \) and \( MM^t \) (where \( M^t \) denotes the transpose of \( M \)) are the degrees of the vertices of \( G \).

Solution:

Let \( G \) be a simple graph with adjacency matrix \( A \) and incidence matrix \( M \).

a) Show that the diagonal entries of \( A^2 \) are the degrees of the vertices of \( G \):

The entry \( (A^2)_{ii} \) represents the \( i \)-th diagonal element of \( A^2 \). The element \( (A^2)_{ii} \) is the sum of the products of the \( i \)-th row of \( A^2 \) with the \( i \)-th column of \( A^2 \). In the context of simple graphs, this is equivalent to counting the number of paths of length 2 from vertex \( i \) to itself, which is the degree of vertex \( i \).

b) Show that the diagonal entries of \( MM^t \) are the degrees of the vertices of \( G \):

Similar to part (a), the entry \( (MM^t)_{ii} \) represents the \( i \)-th diagonal element of \( MM^t \). The element \( (MM^t)_{ii} \) is the sum of the squares of the entries in the \( i \)-th row of \( M \), which corresponds to counting the number of edges incident to vertex \( i \), i.e., the degree of vertex \( i \).

Problem: Rank of Incidence Matrix over GF(2)

Show that the rank over \( GF(2) \) of the incidence matrix of a graph \( G \) is at most \( n - 1 \), with equality if and only if \( G \) is connected.

Solution:

Let \( M \) be the incidence matrix of a graph \( G \) over \( GF(2) \).

The rank of \( M \) over \( GF(2) \) is the maximum number of linearly independent rows (or columns) in \( M \). The rank of \( M \) is at most \( n - 1 \) because \( M \) has \( n \) rows (vertices) and \( n - 1 \) columns (edges).

If \( G \) is connected, then all rows of \( M \) are linearly independent, and the rank is exactly \( n - 1 \).

If \( G \) is not connected, there is at least one linear dependence among the rows, and the rank is less than \( n - 1 \).

Erdős–Gallai Theorem

A sequence of non-negative integers \(d_1 \geq \cdots \geq d_n\) can be represented as the degree sequence of a finite simple graph on \(n\) vertices if and only if \(d_1 + \cdots + d_n\) is even, and for every \(1 \leq k \leq n\), the Erdős–Gallai inequality holds:

\[ \sum_{i=1}^{k}d_{i} \leq k(k-1) + \sum_{i=k+1}^{n}\min(d_{i},k) \]

This condition ensures that the sum of the degrees is even (required for a graph to exist), and the inequality guarantees that the sequence satisfies the Erdős–Gallai theorem for every \(k\) from 1 to \(n\).