HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Disconnected bipartite graph

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
bipartitedisconnectedgraph

Problem

I was searching whether a bipartite graph can have a vertex with 0 degree. I found this, but the answer there says it is possible. Wouldn't that make a graph tripartite?

Also, if a vertex with zero degree exists that will make König's theorem wrong. For example let bipartite graph edges be $(1,a),(2,b),(3,b)$ and $4$ with degree $0$. So maximum matching is 3 and minimum vertex cover is 4 here.

Solution

If graph is bipartite if it is 2-colorable. Equivalently, a graph is bipartite if its vertex set can be partitioned into two sets $A,B$, such that every edge connects a vertex in $A$ and a vertex in $B$. There are no further constraints. In particular, a bipartite graph could be disconnected, have isolated vertices, or even be empty.

In your purported counterexample to König's theorem, a minimum vertex cover is, for example, $\{1,2,3\}$, which indeed has size 3. (Recall that a vertex cover is a set of vertices touching all edges.)

Context

StackExchange Computer Science Q#143258, answer score: 3

Revisions (0)

No revisions yet.