Search Results

I dont't know of a standard name, but it is $G \square K_2$, where $\square$ denotes the Cartesian product.

As I mentioned in the comments, I am not exactly sure what "a finite number of special infinite families of graphs" means, but here is a way to construct an infinite number of counterexamples for all …

The Berge-Fulkerson conjecture holds for planar graphs. Here is a proof. Let $G$ be a bridgeless cubic planar graph. The dual graph $G^*$ is a triangulation. By the Four Colour Theorem, $G^*$ has a …

Let $G$ be a bipartite graph with bipartition $(L,R)$. A necessary and sufficient condition for each vertex on the left to be matched to two vertices on the right is $|N_G(X)| \geq 2|X|$ for all $X \ …

Yes, this is possible. For each prime $p$ and $c \in \{0,1, \dots, p-1\}$ let $A_{c,p}=\{c+kp \mid k \in \mathbb{Z}\}$. Clearly, the set of all $A_{c,p}$ is a clutter $\mathcal C$ with ground set $\ …

It is unlikely that a nice characterization exists because the problem of computing the size of a maximum induced matching is a well-known NP-hard problem, even for bipartite graphs (as mentioned by P …

Here is a bijective proof. Label the vertices of $C_{2n}$ as $1, 2, \dots, n, 1', 2', \dots, n'$ in clockwise order and let $M$ be a matching of size $k<n$ in $C_{2n}$. Since $M$ is not a perfect mat …

An old conjecture of Lovász and Plummer is that for every cubic graph $G$ with no cut-edge, the number of perfect matchings in $G$ is exponential in the number of vertices. Chudnovsky and Seymour pro …

Yes, your conjecture is true, even without the assumption that $G$ does not contain shortcuts. The following proof is due to Sam Fiorini. Proof. Let $P \subseteq \mathbb{R}^{E(G^\star)}$ be the mat …

There is an easy $2$-approximation algorithm for finding a minimum size maximal matching. Simply find any maximal matching. Note that a maximal matching $M$ can be found greedily. Initialize $M=\em …

No. For all $n \geq 3$, there is no $G \in \mathcal{G}_{2n}$ with $f(G)=n!-1$. To see this, note that $f(K_{n,n})=n!$ and $f(K_{n,n}-e)=n!-(n-1)!$, where $K_{n,n}-e$ is $K_{n,n}$ minus an edge. Thu …

Your formal version does not look correct. For each boy $b$, there should be a total order $\leq_b$ on the set of girls $G$ (this is the preference order for $b$) and for each girl $g$, there should …

No, this is not possible. Here is an elaboration of Eric Wofsey's comment. Suppose it is possible and let $M$ be a maximal (under inclusion) matching of $G$ (this exists by Zorn's lemma). Then $| …

Here is an expansion of joro's answer. Claim. $K_{n, n+1}$ is obvious if and only if $n+1$ is even. Proof. If $n+1$ is even, we can add a perfect matching on the vertices on the right to obtain a …

As requested in the comments, there is a standard proof of Hall's Marriage Theorem from the max-flow min-cut theorem. Let $G$ be a bipartite graph satisfying Hall's condition, with bipartition $(A,B) …