The bound $\frac{7}{8}n$ is tight. The example shown below (courtesyimage courtesy of David Eppstein) is a well-known cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ vertices, so the maximum number of vertices covered by a maximum matching is $14$. Note that $\frac{14}{16}=\frac{7}{8}$, and we can get larger examples by taking disjoint unions of this graph.
The bound $\frac{7}{8}n$ is tight. The example shown below (courtesy of David Eppstein) is a well-known cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ vertices, so the maximum number of vertices covered by a maximum matching is $14$. Note that $\frac{14}{16}=\frac{7}{8}$, and we can get larger examples by taking disjoint unions of this graph.
The bound $\frac{7}{8}n$ is tight. The example shown below (image courtesy of David Eppstein) is a well-known cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ vertices, so the maximum number of vertices covered by a maximum matching is $14$. Note that $\frac{14}{16}=\frac{7}{8}$, and we can get larger examples by taking disjoint unions of this graph.
The upperboundbound $\frac{7}{8}n$ is tight. The example shown below (courtesy of David Eppstein) is a well-known cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ vertices, so the maximum number of vertices covered by a maximum matching is $14$. Note that $\frac{14}{16}=\frac{7}{8}$, and we can get larger examples by taking disjoint unions of this graph.
The upperbound $\frac{7}{8}n$ is tight. The example shown below (courtesy of David Eppstein) is a well-known cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ vertices, so the maximum number of vertices covered by a maximum matching is $14$. Note that $\frac{14}{16}=\frac{7}{8}$, and we can get larger examples by taking disjoint unions of this graph.
The bound $\frac{7}{8}n$ is tight. The example shown below (courtesy of David Eppstein) is a well-known cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ vertices, so the maximum number of vertices covered by a maximum matching is $14$. Note that $\frac{14}{16}=\frac{7}{8}$, and we can get larger examples by taking disjoint unions of this graph.
The upperbound $\frac{7}{8}n$ is tight. The example shown below (courtesy of David Eppstein) is a well-known example of a cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ vertices, so the maximum number of vertices covered by a maximum matching is $14$. Note that $\frac{14}{16}=\frac{7}{8}$, and we can get larger examples by taking disjoint unions of this graph.
The upperbound $\frac{7}{8}n$ is tight. The example shown below (courtesy of David Eppstein) is a well-known example of a cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ vertices, so the maximum number of vertices covered by a maximum matching is $14$. Note that $\frac{14}{16}=\frac{7}{8}$, and we can get larger examples by taking disjoint unions of this graph.
The upperbound $\frac{7}{8}n$ is tight. The example shown below (courtesy of David Eppstein) is a well-known cubic (planar) graph that has no perfect matching.
(source: uci.edu)
This graph has $16$ vertices, so the maximum number of vertices covered by a maximum matching is $14$. Note that $\frac{14}{16}=\frac{7}{8}$, and we can get larger examples by taking disjoint unions of this graph.
