Question

Let \(G\) be a graph with \(n\) vertices and \(m\) edges, and let \(v\) be a vertex of \(G\) of degree \(k\) and \(e\) be an edge of \(G\). How many vertices and edges have \(G-e, G-v\) and \(G \backslash e ?\)

Short answer

Removing an edge \(e\) from \(G\) leads to \(n\) vertices and \(m-1\) edges. Removing a vertex \(v\) of degree \(k\) from \(G\) leads to \(n-1\) vertices and \(m-k\) edges. Contracting an edge \(e\) of \(G\) leads to \(n-1\) vertices and \(m-1\) edges.

Step-by-step solution

Analyze the graph G-e

If we remove an edge \(e\) from \(G\), we are not removing any vertices, so the number of vertices remains \(n\). Since we remove one edge, the number of edges is \(m-1\).

Analyze the graph G-v

If we remove a vertex \(v\) from \(G\), we decrease the number of vertices by 1, so the number of vertices becomes \(n-1\). Since a vertex of degree \(k\) is connected to \(k\) edges, when the vertex is removed, \(k\) edges are also removed. Therefore, the number of edges becomes \(m-k\).

Distinguish between G-e and G/v

It's important to notice that \(G \backslash e\) and \(G - e\) are not the same. \(G \backslash e\) means that we are contracting the edge \(e\), not deleting it. When an edge is contracted, the two vertices associated with it merge into one. Therefore, the number of vertices is reduced by 1, becoming \(n-1\) and the number of edges is also reduced by 1, becoming \(m-1\).

Key concepts

Vertices and Edges

In graph theory, understanding the concept of vertices and edges is fundamental. A graph, often represented as \(G\), is comprised of vertices (also known as nodes) and edges (links connecting the nodes). You can imagine the vertices as points and the edges as lines connecting these points.

Here are some essential points to remember:

• Vertices: These are the distinct points on a graph. In our problem, the graph \(G\) has \(n\) vertices.
• Edges: These are the lines or connections between vertices. In graph \(G\), there are \(m\) edges.
• Graph Representation: The graph \(G\) can be depicted using its vertices and edges, described by an ordered pair \(G = (V, E)\), where \(V\) is the set of vertices, and \(E\) is the set of edges.

Understanding how the number of vertices and edges changes when an edge or a vertex is removed or modified, as we will see in the next sections, is key for anyone studying graph theory.

Degrees of Vertices

The degree of a vertex is a crucial concept in graph theory, representing the number of edges connected to a vertex.
The degree tells us how many connections a vertex has, enabling us to understand its level of connectivity in the graph. In our problem, vertex \(v\) has a degree \(k\).

Consider the following details:

• Vertex Degree: This is the number of edges connected to a vertex. For vertex \(v\) in graph \(G\), there are \(k\) edges.
• Graph without a Vertex (\(G-v\)): When vertex \(v\) is removed, all the edges connected to it also disappear, reducing the total edge count by the degree of \(v\) (i.e., \(k\) edges).
• Calculating Degrees: For a clear understanding, if you remove vertex \(v\), the new count of edges becomes \(m-k\), and vertices become \(n-1\) since one vertex and all its connecting edges are gone.

The concept of vertex degrees helps us solve problems efficiently by understanding how graph operations like removal affect its structure.

Edge Contraction

Edge contraction is another significant operation in graph theory where we effectively "merge" two vertices connected by an edge into a single vertex.
This merger reduces the graph's complexity in various scenarios. It's important to differentiate this operation from deleting an edge.

Here’s how edge contraction affects the graph structure:

• Contraction vs Deletion: When we contract an edge \(e\) (denoted as \(G \backslash e\)), the edge is not removed in the usual sense. Instead, the two vertices the edge connects are combined into one, and typically, any parallel edges become loops or are considered merged.
• Graph after Contraction (\(G \backslash e\)): The number of vertices decreases by 1 (from \(n\) to \(n-1\)), and the number of edges typically decreases by 1 (from \(m\) to \(m-1\)), accounting for the edge being contracted.
• Application Example: After contracting an edge in our problem, the resulting graph has one less vertex and one less edge than the original, reflecting these operations precisely.

Edge contraction is particularly useful in simplifying graph visualization or in algorithms that need reduced graph size for efficiency.