graph theory
I need to prove that every graph containing only even vertices is bridgeless.
I understand that an even vertex is one with an even degree. Therefore an even vertex is one which is connected to an even number of vertices.
I also understand an edge $e = uv$ in a connected graph G whose removal creates a disconnected graph is a bridge.
I don't know how to use this to do the proof
🙁
You seem to be proving the wrong result. In this setting, there are two cases:
All odd-degree vertices belong to the same connected component. In this case, there is, by definition, a path from any odd-degree vertex to any other odd-degree vertex.
Two odd degree vertices belong to disjoint components. In this case, there are, by definition, two odd-degree vertices for which there is no path connecting them. And this situation can occur: just take the disjoint union of any two graphs each with an odd degree vertex.
For example, there is no path connecting the two pink vertices below:
This means you're either attempting to prove something that is true by definition, or you're attempting to prove something that is false.
I suspect the correct task is to prove:
Given a connected graph with exactly two odd-degree vertices $u$ and $v$, there is an Eulerian trail from $u$ to $v$.
Since I have been asked to "Please take care in reading my proof.":
WLOG we can assume if k is odd then the graph is not connected.
Here's a connected $5$-vertex graph counterexample:
Then the graph has at least one connected component.
All graphs with at least $1$ vertex have at least one connected component.
For any k=n the endpoints of these connected components have degree 1.
Many graphs don't have "endpoints", i.e., leaf vertices (such as the one below).
If the graph is connected and has an even number of vertices then the vertices have degree (n-1), which is odd.
Here's a counterexample to this claim:
In fact, any connected subgraph of $K_n$, except $K_n$ itself, would be a counterexample.
A connected graph where each vertex has even degree has a Euler circuit. It is now clear that the graph cannot contain a bridge: the existance of a Euler circuit implies that each two vertices are connected by at least two disjoint paths, meaning that deleting one edge cannot disconnect the graph.
Actually, your attempt at solving the problem can be reformulated to a proof showing that a connected graph where each vertex has even degree indeed has a Euler circuit: it must contain a cycle by your reasoning. Since each vertex in the remaining graph still has even degree, the edge set of the graph can be partitioned in cycles. These cycles can be connected to form a Euler circuit since the graph is connected.
Best Answer
Suppose that $e=uv$ is a bridge. When you remove $e$, you reduce the degrees of $u$ and $v$ by $1$ each, so if they were even to begin with, they’re odd in the disconnected graph $G-e$. Let $G_u$ be the component of $G-e$ that contains $u$. Get a contradiction by showing that the sum of the degrees of the vertices of $G_u$ is odd.