Question

Give an example of a graph with at least four vertices, or prove that none exists, such that: (a) There are no vertices of odd degree. (b) There are no vertices of even degree. (c) There is exactly one vertex of odd degree. (d) There is exactly one vertex of even degree. (e) There are exactly two vertices of odd degree.

Short answer

(a) Yes; (b) No; (c) No; (d) Yes; (e) Yes.

Step-by-step solution

Analyzing Graph with No Odd Degree Vertices

For a graph with no vertices of odd degree, all vertices must have even degree. An even degree ensures that the total sum of degrees in the graph is even due to the handshaking lemma, which states that the sum of vertex degrees in a graph is twice the number of edges. A simple example is a cycle with 4 vertices, each vertex with degree 2: a square.

Analyzing Graph with No Even Degree Vertices

For a graph with no vertices of even degree, all vertices must have odd degree. However, this contradicts the handshaking lemma since the sum of degrees (all odd) in any graph must be even. Thus, no such graph can exist.

Analyzing Graph with Exactly One Odd Degree Vertex

According to the handshaking lemma, the number of vertices of odd degree must be even. Thus, it is impossible to have a graph with exactly one vertex of odd degree.

Analyzing Graph with Exactly One Even Degree Vertex

It's possible to construct a graph where only one vertex has an even degree. Consider a graph with vertices labeled A, B, C, and D where: A connects to B and C, B connects to A and D, C connects to A and D, D connects to B and C. Here, vertex A has degree 2 (even) while the others have degree 1 (odd).

Analyzing Graph with Exactly Two Odd Degree Vertices

A graph can have exactly two vertices of odd degree which satisfies the handshaking lemma constraint. An example is a simple path with three vertices: A -- B -- C, where vertices A and C have odd degree (1), and vertex B has even degree (2).

Key concepts

Handshaking Lemma

In graph theory, the handshaking lemma is an essential concept that helps us understand the relationship between vertices and edges. It states that in any undirected graph, the sum of all vertex degrees is equal to twice the number of edges.
This can be expressed mathematically as: \[ \sum_{}deg(v) = 2|E| \]where \( |E| \) is the number of edges. Each edge contributes a degree of 1 to two vertices, hence the factor of 2.

• For graphs with only even degree vertices, the overall sum of degrees is even, complying with the handshaking lemma.
• For graphs with only odd degree vertices, it's impossible because the sum of odd numbers will always be odd, thus contradicting the lemma.
• Therefore, the number of vertices with an odd degree in any graph must always be even.

Graph Properties

Graphs, at their core, are mathematical structures used to model pairwise relations between objects. They have key properties:

• Vertices: The points or nodes where edges meet.
• Edges: The connections between pairs of vertices.

Graph properties may vary based on the types of vertices and edges they comprise:

• Degree of a Vertex: The number of edges incident to that vertex. This can help determine graph types, like cycles, paths, or trees.
• Connectedness: Whether all vertices are accessible from one another via edges.
• Planarity: If the graph can be drawn on a plane without edges crossing.

Understanding these properties is crucial for problem-solving tasks in graph theory.

Vertex Degree

The degree of a vertex in a graph indicates how many edges are connected to that vertex. It is fundamental in analyzing the graph's structure.

• If a graph has vertices of even degree, it simplifies to cyclic structures since each vertex 'returns' to itself.
• Vertices of odd degree complicate the structure as they cannot form a closed cycle on their own.
• A vertex with degree 0 is isolated, meaning it has no connections to other vertices.

The degree is labeled as \(deg(v)\), where \(v\) is the vertex. The sum of all vertex degrees must equal twice the number of edges, due to the handshaking lemma.

Even and Odd Degree

The concept of even and odd degree is pivotal in determining possible graph structures.

• A vertex has an even degree if it is connected by an even number of edges.
• A vertex has an odd degree if it is connected by an odd number of edges.

An important property in graph theory is that the total number of vertices with odd degrees is always even. This is due to the handshaking lemma, which insists that the total sum of degrees is even.
While it may seem arbitrary, this restriction deeply influences the graph's design, ensuring certain configurations, like having just one odd degree vertex, are impossible.
Recognizing these degree conditions can greatly aid in predicting the solvability of graph-related problems.