Unit 2: Graphs and Combinatorics - Subjective Questions

Vertex connectivity: The vertex connectivity of a connected graph is the minimum number of vertices whose removal disconnects the graph or reduces it to a single vertex.

Edge connectivity: The edge connectivity is the minimum number of edges whose removal disconnects .

For the cycle graph :

• Removing any one vertex leaves a path, which remains connected.
• Removing two suitable vertices disconnects the graph. Hence, .
• Removing any one edge leaves a path, which remains connected.
• Removing two edges disconnects the graph. Hence, .

Therefore,

Let be a graph.

• A walk is a sequence of vertices in which every consecutive pair is joined by an edge. Vertices and edges may repeat.
• A trail is a walk in which no edge is repeated, although vertices may repeat.
• A path is a walk in which no vertex is repeated.
• A cycle is a closed path of length at least , with the first and last vertices identical and all other vertices distinct.

For edges :

• is a walk but not a trail because is traversed twice.
• is a trail if its edges are distinct, but it is not a path because repeats.
• is a path.
• is a cycle.

Every path is a trail and every trail is a walk, but the converses need not hold.

For every connected simple graph that is not complete,

where is vertex connectivity, is edge connectivity, and is minimum degree.

Proof of :

• Choose a vertex of minimum degree .
• Removing all edges incident with isolates it.
• These edges form an edge cut.
• Therefore, .

Proof of :

• Let an edge cut of minimum size separate the vertices into nonempty sets and .
• Consider the endpoints in one part of the cut edges.
• Removing a suitable set of these endpoints separates the remaining vertices of from those of .
• The number of removed vertices is at most the number of cut edges.
• Hence, .

Thus,

Vertex form: For two distinct nonadjacent vertices and in a finite graph, the minimum number of vertices whose removal separates from equals the maximum number of internally vertex-disjoint - paths.

Edge form: For two distinct vertices and , the minimum number of edges whose removal separates from equals the maximum number of edge-disjoint - paths.

Importance:

• The theorem gives equivalent cut-based and path-based descriptions of connectivity.
• A graph is -vertex-connected precisely when every pair of appropriate vertices has at least internally vertex-disjoint paths between them.
• A graph is -edge-connected precisely when every pair of vertices has at least edge-disjoint paths between them.
• In communication networks, disjoint paths represent alternative routes, while separating sets represent possible points of failure.

Thus, Menger's theorem connects network robustness with the existence of independent routes.

A matching in a graph is a set of edges no two of which share an endpoint.

• A vertex incident with an edge of is called matched or saturated.
• A maximal matching is a matching to which no additional edge can be added while preserving the matching property.
• A maximum matching is a matching having the largest possible number of edges among all matchings of the graph.
• A perfect matching is a matching that saturates every vertex.

Maximal versus maximum:

• Maximal means inclusion-wise complete: no edge can be added.
• Maximum means largest by cardinality.
• Every maximum matching is maximal, but a maximal matching need not be maximum.

For the path , the matching is maximal but has size . The matching has size and is maximum as well as perfect.

Let be a bipartite graph. For , let denote the set of neighbors of vertices in .

Hall's marriage theorem: There exists a matching that saturates every vertex of if and only if

The condition is necessary because distinct vertices in must be matched to distinct vertices in . Hall's theorem states that this necessary condition is also sufficient.

For , take and . Every nonempty subset has

so . Hall's condition requires for every . The strongest requirement occurs when , giving

Therefore, has a matching saturating the part of size if and only if . It has a perfect matching if and only if .

Let be a matching in a graph. An -augmenting path is a path whose edges alternate between edges outside and edges inside , and whose two endpoints are unmatched by .

Berge's theorem: A matching is maximum if and only if there is no -augmenting path.

Forward direction:

• Suppose an -augmenting path exists.
• The first and last edges of lie outside , so contains one more nonmatching edge than matching edge.
• Replace the matching edges of by its nonmatching edges.
• In symmetric-difference notation, define .
• Then is a matching and .
• Hence, is not maximum.

Reverse direction:

• Suppose is not maximum, and let be a matching with .
• In the graph formed by , every component is an alternating path or an even alternating cycle.
• Since has more edges overall, at least one component contains more edges of than of .
• Such a component is an alternating path beginning and ending with edges of .
• Its endpoints are unmatched by , so it is an -augmenting path.

Therefore, is maximum exactly when no augmenting path exists.

A proper vertex coloring assigns colors to the vertices of a graph so that adjacent vertices receive different colors. The chromatic number is the minimum number of colors required for a proper vertex coloring of .

Complete graph: Every pair of vertices in is adjacent, so every vertex needs a distinct color:

Cycle graph:

• If is even, alternate two colors around the cycle, giving .
• If is odd, two colors cannot close the cycle consistently, but three colors suffice, giving .

Thus,

Nontrivial bipartite graph: Its two independent vertex parts can be assigned two different colors. If it has at least one edge, one color cannot suffice. Therefore,

Greedy coloring algorithm:

1. Choose an ordering of the vertices.
2. Process the vertices in this order.
3. Assign to each vertex the smallest available color not already used by its colored neighbors.

Let the graph have maximum degree . When a vertex is colored, it has at most neighbors. Therefore, at most colors can be forbidden by already colored neighbors.

If a palette of colors is available, at least one color remains available for . The algorithm can consequently color every vertex properly.

Hence,

This bound is attained by complete graphs and by odd cycles when . The number of colors actually used by the greedy algorithm may depend on the chosen vertex ordering.

The chromatic polynomial counts the number of proper vertex colorings of a graph using colors from a set of labeled colors.

For a tree with vertices:

• Choose any vertex as the root. It can be colored in ways.
• Every other vertex has a unique parent.
• Each nonroot vertex may use any color except its parent's color, giving choices.
• There are nonroot vertices.

Therefore,

For a cycle , the chromatic polynomial is

In particular, evaluating at shows that an even cycle has two proper -colorings, while an odd cycle has none.

Vertex coloring assigns colors to vertices so that adjacent vertices have different colors. Its minimum required number is the chromatic number .

Edge coloring assigns colors to edges so that edges sharing an endpoint have different colors. Its minimum required number is the chromatic index, denoted by .

At a vertex of maximum degree , all incident edges must receive distinct colors. Therefore,

Vizing's theorem states that for every finite simple graph,

Consequently, a simple graph belongs to one of two classes:

• Class 1: .
• Class 2: .

For example, an even cycle is Class 1, while an odd cycle is Class 2.

For an -permutation, order matters and repetition is not allowed.

• There are choices for the first position.
• There are choices for the second position.
• Continuing this way gives choices for the last position.

Thus,

For an -combination, order does not matter. Every selected set of elements is counted times among the ordered arrangements. Hence,

The difference is that and represent different permutations but the same combination . Therefore,

For finite sets , , and , the inclusion-exclusion principle states

Let:

• be the multiples of from to .
• be the multiples of .
• be the multiples of .

The individual counts are

The pairwise intersections are counted using least common multiples:

The triple intersection has size

Therefore,

Hence, exactly integers are divisible by at least one of , , or .

Pigeonhole principle: If more than objects are placed into boxes, at least one box contains at least two objects.

Generalized form: If objects are placed into boxes, then some box contains at least

objects.

When an integer is divided by , its remainder must be one of

These possible remainders serve as the boxes. The given integers are the objects. By the pigeonhole principle, at least two integers belong to the same remainder class.

Therefore, there exist two integers and such that

Equivalently, divides their difference:

Let denote the number of binary strings of length with no consecutive s.

Classify valid strings according to their final symbol:

• If a valid string ends in , deleting this leaves any valid string of length . This gives possibilities.
• If it ends in , the preceding symbol must be . Deleting the final block leaves any valid string of length . This gives possibilities.

Therefore,

The initial values are

because the empty string is valid and the length-one strings are and .

This is the Fibonacci recurrence. If and , then

Using Binet's formula,

Assume a solution of the form . Substitution gives

After dividing by , the characteristic equation is

Factoring,

so the distinct characteristic roots are and . The general solution is

Apply the initial conditions:

Subtracting twice the first equation from the second gives , and hence . Therefore,

A substitution check gives

confirming the solution.

The recurrence is

First solve the associated homogeneous recurrence:

which has solution

For a particular solution, try a constant . Substitution gives

so . Thus, the general solution is

Using gives

and hence . Therefore,

The same result can be obtained by iteration:

The ordinary generating function of a sequence is the formal power series

For ,

Start with the geometric series

Differentiate both sides:

The left-hand side can be reindexed as

Therefore,

Analytically, this identity is valid for ; in combinatorics, it may also be treated as an identity of formal power series.

Define the generating function

Multiply the recurrence by and sum for :

Using the initial values,

Hence,

so

Let

Since , partial fractions give

Comparing coefficients of yields Binet's formula:

A variable constrained to take values in a set is represented by the generating function . The coefficient of in the product of the variable generating functions counts solutions whose sum is .

The constraints give:

• For : .
• For : .
• For : .

Their product is

The required number is the coefficient of , which equals the coefficient of in . Using

we obtain

Therefore, the number of solutions is