Graph Theory I - Hoang Anh Duc - MIM - HUS - VNU

Graph Theory II - Hoang Anh Duc - MIM - HUS - VNU

Work 15 (I).

Prove that if \(G\) is a simple undirected graph with exactly 2 vertices \(u, v\) with odd degree then these vertices belongs to a single connected component of \(G\).

Solution:

• Vertices with odd degree: By the handshaking lemma, the number of vertices with odd degrees must be even. Given \(G\) has exactly two vertices \(u\) and \(v\) with odd degrees, there can be no other vertices in \(G\) with odd degree.
• Structure of \(G\): If \(u\) and \(v\) does not belong to the same connected component. then \(u\) and \(v\) would lie in different connected components of \(G\).
  • Consider the connected component \(C_1\) containing \(u\). Since \(u\) has an odd degree, the sum of degress of all vertices in \(C_1\) would be odd, violating the handshaking lemma (as the sum of all degrees in any graph or subgraph must be even).
  • Similarly, the connected component \(C_2\) containing \(v\) would also have an odd degree sum, which again violates the handshaking lemma.
• The contradiction implies that \(u\) and \(v\) cannot lie in separate connected components. Therefore, \(u\) and \(v\) must belong to the same connected component.

Work 20 (I).

Prove that:

Are true for all undirected connected graph \(G = (V, E)\).

Solution:

(1):

• Consider the minimum degree of a vertex in \(G\), denoted as \(\delta(G) = \min_{v \in V} \deg_G(v)\).
• Removing a vertex \(v\) disconnects it from its neighbors. Since \(v\) has exactly \(\deg_G(v)\) neighbors, at most \(\deg_G(v)\) vertices are directly affected when \(v\) is removed.
• The vertex connectivity \(\kappa (G)\) cannot exceed \(\delta (G)\), because the removal of any single vertex affects at most \(\deg_g(v)\) vertices.
• Therefore: \(\kappa(G) \leq \min_{v \in V} \deg_G(v)\).

(2):

• Removing all edges incident to a vertex \(v\) will isolate \(v\) from the rest of the graph. The number of edges incident to \(v\) is \(\deg_G (v)\).
• The edge connectivity \(\lambda (G)\) is the minimum of edges required to disconnect \(G\). Clearly, \(\lambda(G)\) cannot exceed \(\delta (G)\), because disconnecting \(G\) by removing edges must involve at least as many edges as are incident to the vertex with the smallest degree.
• Therefore: \(\lambda(G) \leq \min_{v \in V} \deg_G(v)\).

Work 21 (I).

Find \(\kappa(G)\), \(\lambda(G)\) and \(\min_{v \in V} \deg(v)\) for:

Solution:

• Graph (1)
  • \(\kappa(G) = 2\).
  • \(\lambda(G) = 2\).
  • \(\min_{v \in V} \deg(v) = 2\).
• Graph (2)
  • \(\kappa(G) = 3\).
  • \(\lambda(G) = 3\).
  • \(\min_{v \in V} \deg(v) = 3\).

Work 24 (I).

Find the number of paths with length \(n\) between two distinct vertices of \(K_4\) with \(n\) being 2, 3, 4 and 5.

Solution: 2, 6, 14, 36.

Work 2 (II).

With what value of \(n\) does the graphs \(K_n\), \(C_n\), \(W_n\) and \(Q_n\) has an Eulerian circuit.

Solution:

• \(K_n\): \(n\) is odd.
• \(C_n\): \(n \geq 3\).
• \(W_n\): \(n\) is even.
• \(Q_n\): \(n\) is even.

Work 4 (II).

Find an Eulerian path/circuit in these graphs if any.

Solution:

• Graph (1)
  • Degrees for a, b, c, d, e: 3, 2, 3, 2, 2.
  • Odd vertices: a and c.
  • EP: Exists.
  • EC: None.
• Graph (2)
  • Degrees for a, b, c, d, e: 2, 3, 3, 2, 4.
  • Odd vertices: b and c.
  • EP: Exists.
  • EC: None.
• Graph (3)
  • Degrees for a, b, c, d, e, f: 4, 4, 4, 4, 4, 4.
  • Odd vertices: None
  • EP: Exists.
  • EC: Exists.

Work 6 (II).

Give a graph where it’s Eulerian circuit is also a Hamilton circuit.

Solution: \(C_3\)

Work 7 (II).

Which of the following graphs has a Hamilton circuit and why.

Solution:

• Graph (1)
  • HC: Exists: a -> b -> e -> d -> c -> a.
• Graph (2)
  • HC: None.
• Graph (3)
  • HC: Exists: a -> e -> c -> d -> b -> f -> a.