A 3-regular graph with at most 2 bridges has 1 factor.

707 Views Asked by At

I want to show that every 3-regular graph with at most two bridges, has 1-factor. And I want to use Tutte theorem that says: A graph G has 1-factor iff for every proper subset $S$ of $V(G)$ we have $k_0(G-S)\leq \vert S \vert$ where $k_0(G-S)$ is the number of odd components of $G-S$.

I tried this: Suppose $G_1,...,G_l$ are odd components of $G-S$ (so $k_0(G-S)=l$) and $X_i$ is the number of edges that connects $S$ and $G_i$. $G_i$ has odd vertices that the degree of each of them is $3$. So the sum of it's vertices degrees is odd. On the other hand in $G_i$ the sum of degrees is even. So every $\vert X_i \vert$ must be odd. At most two of them are $1$. So the number of edges connecting $S$ to $G-S$ is at most $3(l-2)+2=3l-4$. On the other hand because every vertex of $S$ has degree $3$, the number of edges connecting $S$ to $G-S$ is at most $3\vert S \vert$. So we have $3l-4\leq 3\vert S \vert \Rightarrow l\leq \vert S \vert +\frac{4}{3}$. I need to show that $l \leq \vert S \vert$. But I don't know how. Would you please help?

1

There are 1 best solutions below

4
On BEST ANSWER

Your approach is good - we just have to be a bit more careful with our counting. First off, by counting degrees we can write $$3|S| = a + b + 2c,$$ where $a$ is the number of edges from $S$ to the odd components of $G-S$, $b$ is the number of edges from $G$ to the even components of $G-S$, and $c$ is the number of edges connecting vertices within $S$. What you wrote then gives $$3l -4 \leq a \leq a + b + 2c = 3|S|.$$ We can't have equality everywhere in the above line, since $3|S|$ is divisible by $3$ while $3l - 4$ is not. This means that either $3l - 4 < a$ or $b + 2c > 0$.

Well, if $3l - 4 < a$, then actually $3l - 2 \leq a$, since $a$ is a sum of $l$ odd numbers and hence $a$ and $l$ have the same parity. This gives us $3l - 2 \leq 3|S|$, so $l \leq |S| + \frac{2}{3}$. Similarly, if $b + 2c > 0,$ then actually $b +2c \geq 2$. This is because $b$ is even (why?). Thus we get $3l - 4 \leq 3|S| - 2$, so again $l \leq |S| + \frac{2}{3}$.

But $l$ is an integer, so $l \leq |S| + \frac{2}{3}$ implies that $l \leq |S|$, which is what we wanted to show.