4_0_3A_Prelude_to_Graph_Theory

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/4%3A_Graph_Theory/4.0%3A_Prelude_to_Graph_Theory

Skip to main content

\\ \def\d{\displaystyle}\\

\\ \newcommand{\f}$$1$${\mathfrak \#1}\\

\\ \newcommand{\s}$$1$${\mathscr \#1}\\

\\ \def\N{\mathbb N}\\

\\ \def\B{\mathbf{B}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\Z{\mathbb Z}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\Q{\mathbb Q}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\R{\mathbb R}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\C{\mathbb C}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\F{\mathbb F}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\A{\mathbb A}\\

\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\

\\ \def\X{\mathbb X}\\

\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\

\\ \def\E{\mathbb E}\\

\\ \def\O{\mathbb O}\\

\\ \def\U{\mathcal U}\\

\\ \def\pow{\mathcal P}\\

\\ \def\inv{^{-1}}\\

\\ \def\nrml{\triangleleft}\\

\\ \def\st{:}\\

\\ \def\\{\widetilde}\\

\\ \def\rem{\mathcal R}\\

\\ \def\sigalg{\$\sigma\$-algebra }\\

\\ \def\Gal{\mbox{Gal}}\\

\\ \def\iff{\leftrightarrow}\\

\\ \def\Iff{\Leftrightarrow}\\

\\ \def\land{\wedge}\\

\\ \def\And{\bigwedge}\\

\\ \def\entry{\entry}\\

\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\

\\ \def\Vee{\bigvee}\\

\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\

\\ \def\imp{\rightarrow}\\

\\ \def\Imp{\Rightarrow}\\

\\ \def\Fi{\Leftarrow}\\

\\ \def\var{\mbox{var}}\\

\\ \def\Th{\mbox{Th}}\\

\\ \def\entry{\entry}\\

\\ \def\sat{\mbox{Sat}}\\

\\ \def\con{\mbox{Con}}\\

\\ \def\iffmodels{\bmodels\models}\\

\\ \def\dbland{\bigwedge \\\\\bigwedge}\\

\\ \def\dom{\mbox{dom}}\\

\\ \def\rng{\mbox{range}}\\

\\ \def\isom{\cong}\\

\\\DeclareMathOperator{\wgt}{wgt}\\

\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\

\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\

\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\

\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\

\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\

\\ \renewcommand{\v}{\vtx{above}{}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\

\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\

\\ \def\ansfilename{practice-answers}\\

\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\

\\ \renewcommand{\bar}{\overline}\\

\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\ \newcommand{\lt}{<}\\

\\ \newcommand{\gt}{>}\\

\\ \newcommand{\amp}{&}\\

\\ \newcommand{\hexbox}$$3$${

  \def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}

  \def\y{-\r\*#1-sin{30}\*\r\*#1}

  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;

  \draw (\x,\y) node{#3};

}\\

\\\renewcommand{\bar}{\overline}\\

\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\\newcommand{\lt}{\<}\\

\\\newcommand{\gt}{\>}\\

\\\newcommand{\amp}{&}\\

Investigate!

In the time of Euler, in the town of Königsberg in Prussia, there was a river containing two islands. The islands were connected to the banks of the river by seven bridges (as seen below). The bridges were very beautiful, and on their days off, townspeople would spend time walking over the bridges. As time passed, a question arose: was it possible to plan a walk so that you cross each bridge once and only once? Euler was able to answer this question. Are you?

\![gt-bridges-art.svg$$(https://math.libretexts.org/@api/deki/files/12903/gt-bridges-art.svg?revision=1&size=bestfit&width=465&height=215)

\![$$(https://math.libretexts.org/images/gt-bridges-art.svg)

Graph Theory is a relatively new area of mathematics, first studied by the super famous mathematician Leonhard Euler in 1735. Since then it has blossomed in to a powerful tool used in nearly every branch of science and is currently an active area of mathematics research.

The problem above, known as the *Seven Bridges of Königsberg*, is the problem that originally inspired graph theory. Consider a “different” problem: Below is a drawing of four dots connected by some lines. Is it possible to trace over each line once and only once (without lifting up your pencil, starting and ending on a dot)?

\![gt-bridges-graph.svg$$(https://math.libretexts.org/@api/deki/files/12904/gt-bridges-graph.svg?revision=1&size=bestfit&width=134&height=122)

\![$$(https://math.libretexts.org/images/gt-bridges-graph.svg)

There is an obvious connection between these two problems. Any path in the dot and line drawing corresponds exactly to a path over the bridges of Königsberg.

Pictures like the dot and line drawing are called graphs . Graphs are made up of a collection of dots called vertices and lines connecting those dots called edges . When two vertices are connected by an edge, we say they are adjacent . The nice thing about looking at graphs instead of pictures of rivers, islands and bridges is that we now have a mathematical object to study. We have distilled the “important” parts of the bridge picture for the purposes of the problem. It does not matter how big the islands are, what the bridges are made out of, if the river contains alligators, etc. All that matters is which land masses are connected to which other land masses, and how many times. This was the great insight that Euler had.

We will return to the question of finding paths through graphs later. But first, here are a few other situations you can represent with graphs:

Example \\\PageIndex{1}\\

Al, Bob, Cam, Dan, and Euclid are all members of the social networking website *Facebook*. The site allows members to be “friends” with each other. It turns out that Al and Cam are friends, as are Bob and Dan. Euclid is friends with everyone. Represent this situation with a graph.

Solution

Each person will be represented by a vertex and each friendship will be represented by an edge. That is, two vertices will be adjacent (there will be an edge between them) if and only if the people represented by those vertices are friends. We get the following graph:

\![gt-facebook.svg$$(https://math.libretexts.org/@api/deki/files/12905/gt-facebook.svg?revision=1&size=bestfit&width=136&height=96)

\![$$(https://math.libretexts.org/images/gt-facebook.svg)

Example \\\PageIndex{1}\\

Each of three houses must be connected to each of three utilities. Is it possible to do this without any of the utility lines crossing?

Solution

We will answer this question later. For now, notice how we would ask this question in the context of graph theory. We are really asking whether it is possible to redraw the graph below without any edges crossing (except at vertices). Think of the top row as the houses, bottom row as the utilities.

\![gt-k33.svg$$(https://math.libretexts.org/@api/deki/files/12906/gt-k33.svg?revision=1&size=bestfit&width=165&height=70)

---

4_1_3A_Definitions

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/4%3A_Graph_Theory/4.1%3A_Definitions

Skip to main content

\\ \def\d{\displaystyle}\\

\\ \newcommand{\f}$$1$${\mathfrak \#1}\\

\\ \newcommand{\s}$$1$${\mathscr \#1}\\

\\ \def\N{\mathbb N}\\

\\ \def\B{\mathbf{B}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\Z{\mathbb Z}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\Q{\mathbb Q}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\R{\mathbb R}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\C{\mathbb C}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\F{\mathbb F}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\A{\mathbb A}\\

\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\

\\ \def\X{\mathbb X}\\

\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\

\\ \def\E{\mathbb E}\\

\\ \def\O{\mathbb O}\\

\\ \def\U{\mathcal U}\\

\\ \def\pow{\mathcal P}\\

\\ \def\inv{^{-1}}\\

\\ \def\nrml{\triangleleft}\\

\\ \def\st{:}\\

\\ \def\\{\widetilde}\\

\\ \def\rem{\mathcal R}\\

\\ \def\sigalg{\$\sigma\$-algebra }\\

\\ \def\Gal{\mbox{Gal}}\\

\\ \def\iff{\leftrightarrow}\\

\\ \def\Iff{\Leftrightarrow}\\

\\ \def\land{\wedge}\\

\\ \def\And{\bigwedge}\\

\\ \def\entry{\entry}\\

\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\

\\ \def\Vee{\bigvee}\\

\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\

\\ \def\imp{\rightarrow}\\

\\ \def\Imp{\Rightarrow}\\

\\ \def\Fi{\Leftarrow}\\

\\ \def\var{\mbox{var}}\\

\\ \def\Th{\mbox{Th}}\\

\\ \def\entry{\entry}\\

\\ \def\sat{\mbox{Sat}}\\

\\ \def\con{\mbox{Con}}\\

\\ \def\iffmodels{\bmodels\models}\\

\\ \def\dbland{\bigwedge \\\\\bigwedge}\\

\\ \def\dom{\mbox{dom}}\\

\\ \def\rng{\mbox{range}}\\

\\ \def\isom{\cong}\\

\\\DeclareMathOperator{\wgt}{wgt}\\

\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\

\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\

\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\

\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\

\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\

\\ \renewcommand{\v}{\vtx{above}{}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\

\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\

\\ \def\ansfilename{practice-answers}\\

\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\

\\ \renewcommand{\bar}{\overline}\\

\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\ \newcommand{\lt}{<}\\

\\ \newcommand{\gt}{>}\\

\\ \newcommand{\amp}{&}\\

\\ \newcommand{\hexbox}$$3$${

  \def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}

  \def\y{-\r\*#1-sin{30}\*\r\*#1}

  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;

  \draw (\x,\y) node{#3};

}\\

\\\renewcommand{\bar}{\overline}\\

\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\\newcommand{\lt}{\<}\\

\\\newcommand{\gt}{\>}\\

\\\newcommand{\amp}{&}\\

Investigate!

Which (if any) of the graphs below are the same?

\![image-59.svg$$(https://math.libretexts.org/@api/deki/files/12907/image-59.svg?revision=1&size=bestfit&width=119&height=62) \![image-60.svg$$(https://math.libretexts.org/@api/deki/files/12909/image-60.svg?revision=1&size=bestfit&width=101&height=96) \![image-61.svg$$(https://math.libretexts.org/@api/deki/files/12908/image-61.svg?revision=1&size=bestfit&width=108&height=107) \![image-62.svg$$(https://math.libretexts.org/@api/deki/files/12910/image-62.svg?revision=1&size=bestfit&width=100&height=95) \![image-63.svg$$(https://math.libretexts.org/@api/deki/files/12911/image-63.svg?revision=1&size=bestfit&width=106&height=105)

\![$$(https://math.libretexts.org/images/image-59.svg) \![$$(https://math.libretexts.org/images/image-60.svg) \![$$(https://math.libretexts.org/images/image-61.svg) \![$$(https://math.libretexts.org/images/image-62.svg) \![$$(https://math.libretexts.org/images/image-63.svg)

The graphs above are unlabeled. Usually we think of a graph as having a specific set of vertices. Which (if any) of the graphs below are the same?

\![image-64.svg$$(https://math.libretexts.org/@api/deki/files/12912/image-64.svg?revision=1&size=bestfit&width=99&height=85) \![image-65.svg$$(https://math.libretexts.org/@api/deki/files/12913/image-65.svg?revision=1&size=bestfit&width=98&height=89) \![image-66.svg$$(https://math.libretexts.org/@api/deki/files/12914/image-66.svg?revision=1&size=bestfit&width=102&height=92) \![image-67.svg$$(https://math.libretexts.org/@api/deki/files/12915/image-67.svg?revision=1&size=bestfit&width=112&height=87)

\![$$(https://math.libretexts.org/images/image-64.svg) \![$$(https://math.libretexts.org/images/image-65.svg) \![$$(https://math.libretexts.org/images/image-66.svg) \![$$(https://math.libretexts.org/images/image-67.svg)

Actually, all the graphs we have seen above are just *drawings* of graphs. A graph is really an abstract mathematical object consisting of two sets \\V\\ and \\E\\ where \\E\\ is a set of 2-element subsets of \\V\text{.}\\ Are the graphs below the same or different?

Graph 1:

• \\V = \\a, b, c, d, e\\\text{,}\\
• \\E = \\\\a,b\\, \\a, c\\, \\a,d\\, \\a,e\\, \\b,c\\, \\d,e\\\\\text{.}\\

Graph 2:

• \\V = \\v_1, v_2, v_3, v_4, v_5\\\text{,}\\
• \\E = \\\\v_1, v_3\\, \\v_1, v_5\\, \\v_2, v_4\\, \\v_2, v_5\\, \\v_3, v_5\\, \\v_4, v_5\\\\\text{.}\\

Before we start studying graphs, we need to agree upon what a graph is. While we almost always think of graphs as pictures (dots connected by lines) this is fairly ambiguous. Do the lines need to be straight? Does it matter how long the lines are or how large the dots are? Can there be two lines connecting the same pair of dots? Can one line connect three dots?

The way we avoid ambiguities in mathematics is to provide concrete and rigorous *definitions*. Crafting good definitions is not easy, but it is incredibly important. The definition is the agreed upon starting point from which all truths in mathematics proceed. Is there a graph with no edges? We have to look at the definition to see if this is possible.

We want our definition to be precise and unambiguous, but it also must agree with our intuition for the objects we are studying. It needs to be useful: we *could* define a graph to be a six legged mammal, but that would not let us solve any problems about bridges. Instead, here is the (now) standard definition of a graph.

Definition

A graph is an ordered pair \\G = (V, E)\\ consisting of a nonempty set \\V\\ (called the vertices ) and a set \\E\\ (called the edges ) of two-element subsets of \\V\text{.}\\

Strange. Nowhere in the definition is there talk of dots or lines. From the definition, a graph could be

\begin{equation\*} (\\a,b,c,d\\, \\\\a,b\\, \\a,c\\, \\b,c\\, \\b,d\\, \\c,d\\\$. \end{equation\*}

Here we have a graph with four vertices (the letters \\a, b, c, d\$ and four edges (the pairs \\\\a,b\\, \\a,c\\, \\b,c\\, \\b,d\\, \\c,d\$\$.

Looking at sets and sets of 2-element sets is difficult to process. That is why we often draw a representation of these sets. We put a dot down for each vertex, and connect two dots with a line precisely when those two vertices are one of the 2-element subsets in our set of edges. Thus one way to draw the graph described above is this:

\![image-68.svg$$(https://math.libretexts.org/@api/deki/files/12916/image-68.svg?revision=1&size=bestfit&width=146&height=110)

\![$$(https://math.libretexts.org/images/image-68.svg)

However we could also have drawn the graph differently. For example either of these:

\![image-69.svg$$(https://math.libretexts.org/@api/deki/files/12917/image-69.svg?revision=1&size=bestfit&width=129&height=98) \![image-70.svg$$(https://math.libretexts.org/@api/deki/files/12918/image-70.svg?revision=1&size=bestfit&width=136&height=64)

\![$$(https://math.libretexts.org/images/image-69.svg) \![$$(https://math.libretexts.org/images/image-70.svg)

We should be careful about what it means for two graphs to be “the same.” Actually, given our definition, this is easy: Are the vertex sets equal? Are the edge sets equal? We know what it means for sets to be equal, and graphs are nothing but a pair of two special sorts of sets.

Example \\\PageIndex{1}\\

Are the graphs below equal?

\begin{equation\*} G_1 = (\\a,b,c\\, \\\\a,b\\, \\b,c\\\$; \qquad G_2 = (\\a,b,c\\, \\\\a,c\\, \\c, b\\\$ \end{equation\*}

equal?

Solution

No. Here the vertex sets of each graph are equal, which is a good start. Also, both graphs have two edges. In the first graph, we have edges \\\\a,b\\\\ and \\\\b,c\\\text{,}\\ while in the second graph we have edges \\\\a,c\\\\ and \\\\c,b\\\text{.}\\ Now we do have \\\\b,c\\ = \\c,b\\\text{,}\\ so that is not the problem. The issue is that \\\\a,b\\ \ne \\a,c\\\text{.}\\ Since the edge sets of the two graphs are not equal (as sets), the graphs are not equal (as graphs).

Even if two graphs are not *equal*, they might be *basically* the same. The graphs in the previous example could be drawn like this:

\![image-71.svg$$(https://math.libretexts.org/@api/deki/files/12919/image-71.svg?revision=1&size=bestfit&width=324&height=78)

\![$$(https://math.libretexts.org/images/image-71.svg)

Graphs that are basically the same (but perhaps not equal) are called isomorphic . We will give a precise definition of this term after a quick example:

Example \\\PageIndex{2}\\

Consider the graphs:

• \\G_1 = \\V_1, E_1\\\\ where \\V_1 = \\a, b, c\\\\ and \\E_1 = \\\\a,b\\, \\a,c\\, \\b,c\\\\\text{;}\\
• \\G_2 = \\V_2, E_2\\\\ where \\V_2 = \\u,v,w\\\\ and \\E_2 = \\\\u,v\\, \\u,w\\, \\v,w\\\\\text{.}\\

Are these graphs the same?

Solution

The two graphs are NOT equal. It is enough to notice that \\V_1 \ne V_2\\ since \\a \in V_1\\ but \\a \notin V_2\text{.}\\ However, both of these graphs consist of three vertices with edges connecting every pair of vertices. We can draw them as follows:

\![$$(https://math.libretexts.org/images/image-72.svg) \![$$(https://math.libretexts.org/images/image-73.svg)

Clearly we want to say these graphs are basically the same, so while they are not equal, they will be *isomorphic*. The reason is we can rename the vertices of one graph and get the second graph as the result.

Intuitively, graphs are isomorphic if they are basically the same, or better yet, if they are the same except for the names of the vertices. To make the concept of renaming vertices precise, we give the following definitions:

Isomorphic Graphs

An isomorphism between two graphs \\G_1\\ and \\G_2\\ is a bijection \\f:V_1 \to V_2\\ between the vertices of the graphs such that if \\\\a,b\\\\ is an edge in \\G_1\\ then \\\\f(a), f(b)\\\\ is an edge in \\G_2\text{.}\\

Two graphs are isomorphic if there is an isomorphism between them. In this case we write \\G_1 \isom G_2\text{.}\\

An isomorphism is simply a function which renames the vertices. It must be a bijection so every vertex gets a new name. These newly named vertices must be connected by edges precisely if they were connected by edges with their old names.

Example \\\PageIndex{3}\\

Decide whether the graphs \\G_1 = \\V_1, E_1\\\\ and \\G_2 = \\V_2, E_2\\\\ are equal or isomorphic.

• \\V_1 = \\a,b,c,d\\\text{,}\\ \\E_1 = \\\\a,b\\, \\a,c\\, \\a,d\\, \\c,d\\\\\\
• \\V_2 = \\a,b,c,d\\\text{,}\\ \\E_2 = \\\\a,b\\, \\a,c\\, \\b,c\\, \\c,d\\\\\\

Solution

The graphs are NOT equal, since \\\\a,d\\ \in E_1\\ but \\\\a,d\\ \notin E_2\text{.}\\ However, since both graphs contain the same number of vertices and same number of edges, they *might* be isomorphic (this is not enough in most cases, but it is a good start).

We can try to build an isomorphism. How about we say \\f(a) = b\text{,}\\ \\f(b) = c\text{,}\\ \\f(c) = d\\ and \\f(d) = a\text{.}\\ This is definitely a bijection, but to make sure that the function is an isomorphism, we must make sure it *respects the edge relation*. In \\G_1\text{,}\\ vertices \\a\\ and \\b\\ are connected by an edge. In \\G_2\text{,}\\ \\f(a) = b\\ and \\f(b) = c\\ are connected by an edge. So far, so good, but we must check the other three edges. The edge \\\\a,c\\\\ in \\G_1\\ corresponds to \\\\f(a), f(c)\\ = \\b,d\\\text{,}\\ but here we have a problem. There is no edge between \\b\\ and \\d\\ in \\G_2\text{.}\\ Thus \\f\\ is NOT an isomorphism.

Not all hope is lost, however. Just because \\f\\ is not an isomorphism does not mean that there is no isomorphism at all. We can try again. At this point it might be helpful to draw the graphs to see how they should match up.

\![image-74.svg$$(https://math.libretexts.org/@api/deki/files/12920/image-74.svg?revision=1&size=bestfit&width=144&height=144) \![image-75.svg$$(https://math.libretexts.org/@api/deki/files/12921/image-75.svg?revision=1&size=bestfit&width=141&height=141)

\![$$(https://math.libretexts.org/images/image-74.svg) \![$$(https://math.libretexts.org/images/image-75.svg)

Alternatively, notice that in \\G_1\text{,}\\ the vertex \\a\\ is adjacent to every other vertex. In \\G_2\text{,}\\ there is also a vertex with this property: \\c\text{.}\\ So build the bijection \\g:V_1 \to V_2\\ by defining \\g(a) = c\\ to start with. Next, where should we send \\b\text{?}\\ In \\G_1\text{,}\\ the vertex \\b\\ is only adjacent to vertex \\a\text{.}\\ There is exactly one vertex like this in \\G_2\text{,}\\ namely \\d\text{.}\\ So let \\g(b) = d\text{.}\\ As for the last two, in this example, we have a free choice: let \\g(c) = b\\ and \\g(d) = a\\ (switching these would be fine as well).

We should check that this really is an isomorphism. It is definitely a bijection. We must make sure that the edges are respected. The four edges in \\G_1\\ are

\begin{equation\*} \\a,b\\, \\a,c\\, \\a,d\\, \\c,d\\ \end{equation\*}

Under the proposed isomorphism these become

\begin{equation\*} \\g(a), g(b)\\, \\g(a), g(c)\\, \\g(a), g(d)\\, \\g(c), g(d)\\ \end{equation\*} \begin{equation\*} \\c,d\\, \\c,b\\, \\c,a\\, \\b,a\\ \end{equation\*}

which are precisely the edges in \\G_2\text{.}\\ Thus \\g\\ is an isomorphism, so \\G_1 \cong G_2\\

Sometimes we will talk about a graph with a special name (like \\K_n\\ or the *Peterson graph*) or perhaps draw a graph without any labels. In this case we are really referring to *all* graphs isomorphic to any copy of that particular graph. A collection of isomorphic graphs is often called an isomorphism class .¹This is not unlike geometry, where we might have more than one copy of a particular triangle. There instead of *isomorphic* we say *congruent*.

There are other relationships between graphs that we care about, other than equality and being isomorphic. For example, compare the following pair of graphs:

\![image-76.svg$$(https://math.libretexts.org/@api/deki/files/12922/image-76.svg?revision=1&size=bestfit&width=135&height=117)\![image-77.svg$$(https://math.libretexts.org/@api/deki/files/12923/image-77.svg?revision=1&size=bestfit&width=111&height=110)

\![$$(https://math.libretexts.org/images/image-76.svg) \![$$(https://math.libretexts.org/images/image-77.svg)

These are definitely not isomorphic, but notice that the graph on the right looks like it might be part of the graph on the left, especially if we draw it like this:

\![image-78.svg$$(https://math.libretexts.org/@api/deki/files/12924/image-78.svg?revision=1&size=bestfit&width=125&height=111)

\![$$(https://math.libretexts.org/images/image-78.svg)

We would like to say that the smaller graph is a *subgraph* of the larger.

We should give a careful definition of this. In fact, there are two reasonable notions for what a subgroup should mean.

Subgraphs

We say that \\G_1 = (V_1, E_1)\\ is a subgraph of \\G_2 = (V_2, E_2)\\ provided \\V_1 \subseteq V_2\\ and \\E_1 \subseteq E_2\text{.}\\

We say that \\G_1 = (V_1, E_1)\\ is an induced subgraph of \\G_2 = (V_2, E_2)\\ provided \\V_1 \subseteq V_2\\ and \\E_1\\ contains all edges of \\E_2\\ which are subsets of \\V_1\text{.}\\

Notice that every induced subgraph is also an ordinary subgraph, but not conversely. Think of a subgraph as the result of deleting some vertices and edges from the larger graph. For the subgraph to be an induced subgraph, we can still delete vertices, but now we only delete those edges that included the deleted vertices.

Example \\\PageIndex{4}\\

Consider the graphs:

\![image-82.svg$$(https://math.libretexts.org/@api/deki/files/12928/image-82.svg?revision=1&size=bestfit&width=103&height=123) \![image-79.svg$$(https://math.libretexts.org/@api/deki/files/12925/image-79.svg?revision=1&size=bestfit&width=100&height=120) \![image-80.svg$$(https://math.libretexts.org/@api/deki/files/12926/image-80.svg?revision=1&size=bestfit&width=110&height=90) \![image-81.svg$$(https://math.libretexts.org/@api/deki/files/12927/image-81.svg?revision=1&size=bestfit&width=107&height=128)

\![$$(https://math.libretexts.org/images/image-79.svg) \![$$(https://math.libretexts.org/images/image-80.svg) \![$$(https://math.libretexts.org/images/image-81.svg) \![$$(https://math.libretexts.org/images/image-82.svg)

Here both \\G_2\\ and \\G_3\\ are subgraphs of \\G_1\text{.}\\ But only \\G_2\\ is an *induced* subgraph. Every edge in \\G_1\\ that connects vertices in \\G_2\\ is also an edge in \\G_2\text{.}\\ In \\G_3\text{,}\\ the edge \\\\a,b\\\\ is in \\E_1\\ but not \\E_3\text{,}\\ even though vertices \\a\\ and \\b\\ are in \\V_3\text{.}\\

The graph \\G_4\\ is NOT a subgraph of \\G_1\text{,}\\ even though it looks like all we did is remove vertex \\e\text{.}\\ The reason is that in \\E_4\\ we have the edge \\\\c,f\\\\ but this is not an element of \\E_1\text{,}\\ so we don't have the required \\E_4 \subseteq E_1\text{.}\\

Back to some basic graph theory definitions. Notice that all the graphs we have drawn above have the property that no pair of vertices is connected more than once, and no vertex is connected to itself. Graphs like these are sometimes called simple , although we will just call them *graphs*. This is because our definition for a graph says that the edges form a set of 2-element subsets of the vertices. Remember that it doesn't make sense to say a set contains an element more than once. So no pair of vertices can be connected by an edge more than once. Also, since each edge must be a set containing two vertices, we cannot have a single vertex connected to itself by an edge.

That said, there are times we want to consider double (or more) edges and single edge loops. For example, the “graph” we drew for the Bridges of Königsberg problem had double edges because there really are two bridges connecting a particular island to the near shore. We will call these objects multigraphs . This is a good name: a *multiset* is a set in which we are allowed to include a single element multiple times.

The graphs above are also connected : you can get from any vertex to any other vertex by following some path of edges. A graph that is not connected can be thought of as two separate graphs drawn close together. For example, the following graph is NOT connected because there is no path from \\a\\ to \\b\text{:}\\

\![ex-gt-non-connected.svg$$(https://math.libretexts.org/@api/deki/files/12929/ex-gt-non-connected.svg?revision=1&size=bestfit&width=217&height=124)

\![$$(https://math.libretexts.org/images/ex-gt-non-connected.svg)

Most of the time, it makes sense to treat non-connected graphs as separate graphs (think of the above graph as two squares), so unless otherwise stated, we will assume all our graphs are connected.

Vertices in a graph do not always have edges between them. If we add all possible edges, then the resulting graph is called complete . That is, a graph is complete if every pair of vertices is connected by an edge. Since a graph is determined completely by which vertices are adjacent to which other vertices, there is only one complete graph with a given number of vertices. We give these a special name: \\K_n\\ is the complete graph on \\n\\ vertices.

Each vertex in \\K_n\\ is adjacent to \\n-1\\ other vertices. We call the number of edges emanating from a given vertex the degree of that vertex. So every vertex in \\K_n\\ has degree \\n-1\text{.}\\ How many edges does \\K_n\\ have? One might think the answer should be \\n(n-1)\text{,}\\ since we count \\n-1\\ edges \\n\\ times (once for each vertex). However, each edge is incident to 2 vertices, so we counted every edge exactly twice. Thus there are \\n(n-1)/2\\ edges in \\K_n\text{.}\\ Alternatively, we can say there are \\{n \choose 2}\\ edges, since to draw an edge we must choose 2 of the \\n\\ vertices.

In general, if we know the degrees of all the vertices in a graph, we can find the number of edges. The sum of the degrees of all vertices will always be *twice* the number of edges, since each edge adds to the degree of two vertices. Notice this means that the sum of the degrees of all vertices in any graph must be even!

Example \\\PageIndex{5}\\

At a recent math seminar, 9 mathematicians greeted each other by shaking hands. Is it possible that each mathematician shook hands with exactly 7 people at the seminar?

Solution

It seems like this should be possible. Each mathematician chooses one person to not shake hands with. But this cannot happen. We are asking whether a graph with 9 vertices can have each vertex have degree 7. If such a graph existed, the sum of the degrees of the vertices would be \\9\cdot 7 = 63\text{.}\\ This would be twice the number of edges (handshakes) resulting in a graph with \\31.5\\ edges. That is impossible. Thus at least one (in fact an odd number) of the mathematicians must have shaken hands with an *even* number of people at the seminar.

One final definition: we say a graph is bipartite if the vertices can be divided into two sets, \\A\\ and \\B\text{,}\\ with no two vertices in \\A\\ adjacent and no two vertices in \\B\\ adjacent. The vertices in \\A\\ can be adjacent to some or all of the vertices in \\B\text{.}\\ If each vertex in \\A\\ is adjacent to all the vertices in \\B\text{,}\\ then the graph is a complete bipartite graph , and gets a special name: \\K\_{m,n}\text{,}\\ where \\\|A\| = m\\ and \\\|B\| = n\text{.}\\ The graph in the houses and utilities puzzle is \\K\_{3,3}\text{.}\\

Named Graphs

Some graphs are used more than others, and get special names.

• \\K_n\\: The complete graph on \\n\\ vertices.
• \\K\_{m,n}\\: The complete bipartite graph with sets of \\m\\ and \\n\\ vertices.
• \\C_n\\: The cycle on \\n\\ vertices, just one big loop.
• \\P_n\\: The path on \\n\\ vertices, just one long path.

There are a lot of definitions to keep track of in graph theory. Here is a glossary of the terms we have already used and will soon encounter.

Graph Theory Definitions

• Graph: A collection of vertices, some of which are connected by edges. More precisely, a pair of sets \\V\\ and \\E\\ where \\V\\ is a set of vertices and \\E\\ is a set of 2-element subsets of \\V\text{.}\\
• Adjacent: Two vertices are adjacent if they are connected by an edge. Two edges are adjacent if they share a vertex.
• Bipartite graph: A graph for which it is possible to divide the vertices into two disjoint sets such that there are no edges between any two vertices in the same set.
• Complete bipartite graph: A bipartite graph for which every vertex in the first set is adjacent to every vertex in the second set.
• Complete graph: A graph in which every pair of vertices is adjacent.
• Connected: A graph is connected if there is a path from any vertex to any other vertex.
• Chromatic number: The minimum number of colors required in a proper vertex coloring of the graph.
• Cycle: A path (see below) that starts and stops at the same vertex, but contains no other repeated vertices.
• Degree of a vertex: The number of edges incident to a vertex.
• Euler path: A walk which uses each edge exactly once.
• Euler circuit: An Euler path which starts and stops at the same vertex.
• Multigraph: A multigraph is just like a graph but can contain multiple edges between two vertices as well as single edge loops (that is an edge from a vertex to itself).
• Planar: A graph which can be drawn (in the plane) without any edges crossing.
• Subgraph: We say that \\H\\ is a subgraph of \\G\\ if every vertex and edge of \\H\\ is also a vertex or edge of \\G\text{.}\\ We say \\H\\ is an induced subgraph of \\G\\ if every vertex of \\H\\ is a vertex of \\G\\ and each pair of vertices in \\H\\ are adjacent in \\H\\ if and only if they are adjacent in \\G\text{.}\\
• Tree: A (connected) graph with no cycles. (A non-connected graph with no cycles is called a forest.) The vertices in a tree with degree 1 are called leaves.
• Vertex coloring: An assignment of colors to each of the vertices of a graph. A vertex coloring is proper if adjacent vertices are always colored differently.
• Walk: A sequence of vertices such that consecutive vertices (in the sequence) are adjacent (in the graph). A walk in which no vertex is repeated is called simple

---

4_2_3A_Planar_Graphs

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/4%3A_Graph_Theory/4.2%3A_Planar_Graphs

Skip to main content

\\ \def\d{\displaystyle}\\

\\ \newcommand{\f}$$1$${\mathfrak \#1}\\

\\ \newcommand{\s}$$1$${\mathscr \#1}\\

\\ \def\N{\mathbb N}\\

\\ \def\B{\mathbf{B}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\Z{\mathbb Z}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\Q{\mathbb Q}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\R{\mathbb R}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\C{\mathbb C}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\F{\mathbb F}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\A{\mathbb A}\\

\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\

\\ \def\X{\mathbb X}\\

\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\

\\ \def\E{\mathbb E}\\

\\ \def\O{\mathbb O}\\

\\ \def\U{\mathcal U}\\

\\ \def\pow{\mathcal P}\\

\\ \def\inv{^{-1}}\\

\\ \def\nrml{\triangleleft}\\

\\ \def\st{:}\\

\\ \def\\{\widetilde}\\

\\ \def\rem{\mathcal R}\\

\\ \def\sigalg{\$\sigma\$-algebra }\\

\\ \def\Gal{\mbox{Gal}}\\

\\ \def\iff{\leftrightarrow}\\

\\ \def\Iff{\Leftrightarrow}\\

\\ \def\land{\wedge}\\

\\ \def\And{\bigwedge}\\

\\ \def\entry{\entry}\\

\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\

\\ \def\Vee{\bigvee}\\

\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\

\\ \def\imp{\rightarrow}\\

\\ \def\Imp{\Rightarrow}\\

\\ \def\Fi{\Leftarrow}\\

\\ \def\var{\mbox{var}}\\

\\ \def\Th{\mbox{Th}}\\

\\ \def\entry{\entry}\\

\\ \def\sat{\mbox{Sat}}\\

\\ \def\con{\mbox{Con}}\\

\\ \def\iffmodels{\bmodels\models}\\

\\ \def\dbland{\bigwedge \\\\\bigwedge}\\

\\ \def\dom{\mbox{dom}}\\

\\ \def\rng{\mbox{range}}\\

\\ \def\isom{\cong}\\

\\\DeclareMathOperator{\wgt}{wgt}\\

\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\

\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\

\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\

\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\

\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\

\\ \renewcommand{\v}{\vtx{above}{}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\

\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\

\\ \def\ansfilename{practice-answers}\\

\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\

\\ \renewcommand{\bar}{\overline}\\

\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\ \newcommand{\lt}{<}\\

\\ \newcommand{\gt}{>}\\

\\ \newcommand{\amp}{&}\\

\\ \newcommand{\hexbox}$$3$${

  \def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}

  \def\y{-\r\*#1-sin{30}\*\r\*#1}

  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;

  \draw (\x,\y) node{#3};

}\\

\\\renewcommand{\bar}{\overline}\\

\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\\newcommand{\lt}{\<}\\

\\\newcommand{\gt}{\>}\\

\\\newcommand{\amp}{&}\\

!

When a connected graph can be drawn without any edges crossing, it is called planar . When a planar graph is drawn in this way, it divides the plane into regions called faces .

1. Draw, if possible, two different planar graphs with the same number of vertices, edges, and faces.

2. Draw, if possible, two different planar graphs with the same number of vertices and edges, but a different number of faces.

When is it possible to draw a graph so that none of the edges cross? If this *is* possible, we say the graph is planar (since you can draw it on the *plane*).

Notice that the definition of planar includes the phrase “it is possible to.” This means that even if a graph does not look like it is planar, it still might be. Perhaps you can redraw it in a way in which no edges cross. For example, this is a planar graph:

\![image-101.svg$$(https://math.libretexts.org/@api/deki/files/12850/image-101.svg?revision=1&size=bestfit&width=177&height=119)

\![$$(https://math.libretexts.org/images/image-101.svg)

That is because we can redraw it like this:

\![image-102.svg$$(https://math.libretexts.org/@api/deki/files/12851/image-102.svg?revision=1&size=bestfit&width=200&height=160)

\![$$(https://math.libretexts.org/images/image-102.svg)

The graphs are the same, so if one is planar, the other must be too. However, the original drawing of the graph was not a planar representation of the graph.

When a planar graph is drawn without edges crossing, the edges and vertices of the graph divide the plane into regions. We will call each region a face . The graph above has 3 faces (yes, we *do* include the “outside” region as a face). The number of faces does not change no matter how you draw the graph (as long as you do so without the edges crossing), so it makes sense to ascribe the number of faces as a property of the planar graph.

WARNING: you can only count faces when the graph is drawn in a planar way. For example, consider these two representations of the same graph:

\![image-103.svg$$(https://math.libretexts.org/@api/deki/files/12853/image-103.svg?revision=1&size=bestfit&width=102&height=102) \![image-104.svg$$(https://math.libretexts.org/@api/deki/files/12852/image-104.svg?revision=1&size=bestfit&width=132&height=132)

\![$$(https://math.libretexts.org/images/image-103.svg) \![$$(https://math.libretexts.org/images/image-104.svg)

If you try to count faces using the graph on the left, you might say there are 5 faces (including the outside). But drawing the graph with a planar representation shows that in fact there are only 4 faces.

There is a connection between the number of vertices (\\v\$, the number of edges (\\e\$ and the number of faces (\\f\$ in any connected planar graph. This relationship is called Euler's formula.

Definition: Euler's Formula for Planar Graphs

For any (connected) planar graph with \\v\\ vertices, \\e\\ edges and \\f\\ faces, we have

\begin{equation\*} v-e + f = 2 \end{equation\*}

Why is Euler's formula true? One way to convince yourself of its validity is to draw a planar graph step by step. Start with the graph \\P_2\text{:}\\

\![image-105.svg$$(https://math.libretexts.org/@api/deki/files/12854/image-105.svg?revision=1&size=bestfit&width=81&height=77)

\![$$(https://math.libretexts.org/images/image-105.svg)

Any connected graph (besides just a single isolated vertex) must contain this subgraph. Now build up to your graph by adding edges and vertices. Each step will consist of either adding a new vertex connected by a new edge to part of your graph (so creating a new “spike”) or by connecting two vertices already in the graph with a new edge (completing a circuit).

\![image-106.svg$$(https://math.libretexts.org/@api/deki/files/12855/image-106.svg?revision=1&size=bestfit&width=187&height=127)\![image-107.svg$$(https://math.libretexts.org/@api/deki/files/12856/image-107.svg?revision=1&size=bestfit&width=130&height=128)

\![$$(https://math.libretexts.org/images/image-106.svg) \![$$(https://math.libretexts.org/images/image-107.svg)

What do these “moves” do? When adding the spike, the number of edges increases by 1, the number of vertices increases by one, and the number of faces remains the same. But this means that \\v - e + f\\ does not change. Completing a circuit adds one edge, adds one face, and keeps the number of vertices the same. So again, \\v - e + f\\ does not change.

Since we can build any graph using a combination of these two moves, and doing so never changes the quantity \\v - e + f\text{,}\\ that quantity will be the same for all graphs. But notice that our starting graph \\P_2\\ has \\v = 2\text{,}\\ \\e = 1\\ and \\f = 1\text{,}\\ so \\v - e + f = 2\text{.}\\ This argument is essentially a proof by induction. A good exercise would be to rewrite it as a formal induction proof.

Non-planar Graphs

!

For the complete graphs \\K_n\text{,}\\ we would like to be able to say something about the number of vertices, edges, and (if the graph is planar) faces. Let's first consider \\K_3\text{:}\\

1. How many vertices does \\K_3\\ have? How many edges?

2. If \\K_3\\ is planar, how many faces should it have?

Repeat parts (1) and (2) for \\K_4\text{,}\\ \\K_5\text{,}\\ and \\K\_{23}\text{.}\\

What about complete bipartite graphs? How many vertices, edges, and faces (if it were planar) does \\K\_{7,4}\\ have? For which values of \\m\\ and \\n\\ are \\K_n\\ and \\K\_{m,n}\\ planar?

Not all graphs are planar. If there are too many edges and too few vertices, then some of the edges will need to intersect. The first time this happens is in \\K_5\text{.}\\

\![image-108.svg$$(https://math.libretexts.org/@api/deki/files/12930/image-108.svg?revision=1&size=bestfit&width=135&height=128)

\![$$(https://math.libretexts.org/images/image-108.svg)

If you try to redraw this without edges crossing, you quickly get into trouble. There seems to be one edge too many. In fact, we can prove that no matter how you draw it, \\K_5\\ will always have edges crossing.

Theorem \\\PageIndex{1}\\

\\K_5\\ is not planar.

Proof

The proof is by contradiction. So assume that \\K_5\\ is planar. Then the graph must satisfy Euler's formula for planar graphs. \\K_5\\ has 5 vertices and 10 edges, so we get

\begin{equation\*} 5 - 10 + f = 2 \end{equation\*}

which says that if the graph is drawn without any edges crossing, there would be \\f = 7\\ faces.

Now consider how many edges surround each face. Each face must be surrounded by at least 3 edges. Let \\B\\ be the total number of *boundaries* around all the faces in the graph. Thus we have that \\B \ge 3f\text{.}\\ But also \\B = 2e\text{,}\\ since each edge is used as a boundary exactly twice. Putting this together we get

\begin{equation\*} 3f \le 2e \end{equation\*}

But this is impossible, since we have already determined that \\f = 7\\ and \\e = 10\text{,}\\ and \\21 \not\le 20\text{.}\\ This is a contradiction so in fact \\K_5\\ is not planar.

\\\square\\

The other simplest graph which is not planar is \\K\_{3,3}\\

\![image-109.svg$$(https://math.libretexts.org/@api/deki/files/12931/image-109.svg?revision=1&size=bestfit&width=131&height=81)

\![$$(https://math.libretexts.org/images/image-109.svg)

Proving that \\K\_{3,3}\\ is not planar answers the houses and utilities puzzle: it is not possible to connect each of three houses to each of three utilities without the lines crossing.

Theorem \\\PageIndex{2}\\

\\K\_{3,3}\\ is not planar.

Proof

Again, we proceed by contradiction. Suppose \\K\_{3,3}\\ were planar. Then by Euler's formula there will be 5 faces, since \\v = 6\text{,}\\ \\e = 9\text{,}\\ and \\6 - 9 + f = 2\text{.}\\

How many boundaries surround these 5 faces? Let \\B\\ be this number. Since each edge is used as a boundary twice, we have \\B = 2e\text{.}\\ Also, \\B \ge 4f\\ since each face is surrounded by 4 or more boundaries. We know this is true because \\K\_{3,3}\\ is bipartite, so does not contain any 3-edge cycles. Thus

\begin{equation\*} 4f \le 2e. \end{equation\*}

But this would say that \\20 \le 18\text{,}\\ which is clearly false. Thus \\K\_{3,3}\\ is not planar.

\\\square\\

Note the similarities and differences in these proofs. Both are proofs by contradiction, and both start with using Euler's formula to derive the (supposed) number of faces in the graph. Then we find a relationship between the number of faces and the number of edges based on how many edges surround each face. This is the only difference. In the proof for \\K_5\text{,}\\ we got \\3f \le 2e\\ and for \\K\_{3,3}\\ we go \\4f \le 2e\text{.}\\ The coefficient of \\f\\ is the key. It is the smallest number of edges which could surround any face. If some number of edges surround a face, then these edges form a cycle. So that number is the size of the smallest cycle in the graph.

In general, if we let \\g\\ be the size of the smallest cycle in a graph (\\g\\ stands for *girth*, which is the technical term for this) then for any planar graph we have \\gf \le 2e\text{.}\\ When this disagrees with Euler's formula, we know for sure that the graph cannot be planar.

Polyhedra

Investigate!

A cube is an example of a convex polyhedron. It contains 6 identical squares for its faces, 8 vertices, and 12 edges. The cube is a regular polyhedron (also known as a Platonic solid ) because each face is an identical regular polygon and each vertex joins an equal number of faces.

There are exactly four other regular polyhedra: the tetrahedron, octahedron, dodecahedron, and icosahedron with 4, 8, 12 and 20 faces respectively. How many vertices and edges do each of these have?

Another area of mathematics where you might have heard the terms “vertex,” “edge,” and “face” is geometry. A polyhedron is a geometric solid made up of flat polygonal faces joined at edges and vertices. We are especially interested in convex polyhedra, which means that any line segment connecting two points on the interior of the polyhedron must be entirely contained inside the polyhedron.²

An alternative definition for convex is that the internal angle formed by any two faces must be less than \\180 ^o\\.

Notice that since \\8 - 12 + 6 = 2\text{,}\\ the vertices, edges and faces of a cube satisfy Euler's formula for planar graphs. This is not a coincidence.

We can represent a cube as a planar graph by projecting the vertices and edges onto the plane. One such projection looks like this:

\![image-110.svg$$(https://math.libretexts.org/@api/deki/files/12932/image-110.svg?revision=1&size=bestfit&width=143&height=143)

\![$$(https://math.libretexts.org/images/image-110.svg)

In fact, *every* convex polyhedron can be projected onto the plane without edges crossing. Think of placing the polyhedron inside a sphere, with a light at the center of the sphere. The edges and vertices of the polyhedron cast a shadow onto the interior of the sphere. You can then cut a hole in the sphere in the middle of one of the projected faces and “stretch” the sphere to lay down flat on the plane. The face that was punctured becomes the “outside” face of the planar graph.

The point is, we can apply what we know about graphs (in particular planar graphs) to convex polyhedra. Since every convex polyhedron can be represented as a planar graph, we see that Euler's formula for planar graphs holds for all convex polyhedra as well. We also can apply the same sort of reasoning we use for graphs in other contexts to convex polyhedra. For example, we know that there is no convex polyhedron with 11 vertices all of degree 3, as this would make 33/2 edges.

Example \\\PageIndex{3}\\

Is there a convex polyhedron consisting of three triangles and six pentagons? What about three triangles, six pentagons and five heptagons (7-sided polygons)?

Solution

How many edges would such polyhedra have? For the first proposed polyhedron, the triangles would contribute a total of 9 edges, and the pentagons would contribute 30. However, this counts each edge twice (as each edge borders exactly two faces), giving 39/2 edges, an impossibility. There is no such polyhedron.

The second polyhedron does not have this obstacle. The extra 35 edges contributed by the heptagons give a total of 74/2 = 37 edges. So far so good. Now how many vertices does this supposed polyhedron have? We can use Euler's formula. There are 14 faces, so we have \\v - 37 + 14 = 2\\ or equivalently \\v = 25\text{.}\\ But now use the vertices to count the edges again. Each vertex must have degree *at least* three (that is, each vertex joins at least three faces since the interior angle of all the polygons must be less that \\180^\circ\$, so the sum of the degrees of vertices is at least 75. Since the sum of the degrees must be exactly twice the number of edges, this says that there are strictly more than 37 edges. Again, there is no such polyhedron.

To conclude this application of planar graphs, consider the regular polyhedra. Above we claimed there are only five. How do we know this is true? We can prove it using graph theory.

Theorem \\\PageIndex{3}\\: regular polyhedra

There are exactly five regular polyhedra.

Proof

Recall that a regular polyhedron has all of its faces identical regular polygons, and that each vertex has the same degree. Consider the cases, broken up by what the regular polygon might be.

Case 1: Each face is a triangle. Let \\f\\ be the number of faces. There are then \\3f/2\\ edges. Using Euler's formula we have \\v - 3f/2 + f = 2\\ so \\v = 2 + f/2\text{.}\\ Now each vertex has the same degree, say \\k\text{.}\\ So the number of edges is also \\kv/2\text{.}\\ Putting this together gives

\begin{equation\*} e = \frac{3f}{2} = \frac{k(2+f/2)}{2} \end{equation\*}

which says

\begin{equation\*} k = \frac{6f}{4+f} \end{equation\*}

We need \\k\\ and \\f\\ to both be positive integers. Note that \\\frac{6f}{4+f}\\ is an increasing function for positive \\f\text{,}\\ and has a horizontal asymptote at 6. Thus the only possible values for \\k\\ are 3, 4, and 5. Each of these are possible. To get \\k = 3\text{,}\\ we need \\f = 4\\ (this is the tetrahedron). For \\k = 4\\ we take \\f = 8\\ (the octahedron). For \\k = 5\\ take \\f = 20\\ (the icosahedron). Thus there are exactly three regular polyhedra with triangles for faces.

Case 2: Each face is a square. Now we have \\e = 4f/2 = 2f\text{.}\\ Using Euler's formula we get \\v = 2 + f\text{,}\\ and counting edges using the degree \\k\\ of each vertex gives us

\begin{equation\*} e = 2f = \frac{k(2+f)}{2} \end{equation\*}

Solving for \\k\\ gives

\begin{equation\*} k = \frac{4f}{2+f} = \frac{8f}{4+2f} \end{equation\*}

This is again an increasing function, but this time the horizontal asymptote is at \\k = 4\text{,}\\ so the only possible value that \\k\\ could take is 3. This produces 6 faces, and we have a cube. There is only one regular polyhedron with square faces.

Case 3: Each face is a pentagon. We perform the same calculation as above, this time getting \\e = 5f/2\\ so \\v = 2 + 3f/2\text{.}\\ Then

\begin{equation\*} e = \frac{5f}{2} = \frac{k(2+3f/2)}{2} \end{equation\*}

so

\begin{equation\*} k = \frac{10f}{4+3f} \end{equation\*}

Now the horizontal asymptote is at \\\frac{10}{3}\text{.}\\ This is less than 4, so we can only hope of making \\k = 3\text{.}\\ We can do so by using 12 pentagons, getting the dodecahedron. This is the only regular polyhedron with pentagons as faces.

Case 4: Each face is an \\n\\-gon with \\n \ge 6\text{.}\\ Following the same procedure as above, we deduce that

\begin{equation\*} k = \frac{2nf}{4+(n-2)f} \end{equation\*}

which will be increasing to a horizontal asymptote of \\\frac{2n}{n-2}\text{.}\\ When \\n = 6\text{,}\\ this asymptote is at \\k = 3\text{.}\\ Any larger value of \\n\\ will give an even smaller asymptote. Therefore no regular polyhedra exist with faces larger than pentagons.³Notice that you can tile the plane with hexagons. This is an infinite planar graph; each vertex has degree 3. These infinitely many hexagons correspond to the limit as \\f \to \infty\\ to make \\k = 3\text{.}\\

\\\square\\

---

4_3_3A_Coloring

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/4%3A_Graph_Theory/4.3%3A_Coloring

Skip to main content

\\ \def\d{\displaystyle}\\

\\ \newcommand{\f}$$1$${\mathfrak \#1}\\

\\ \newcommand{\s}$$1$${\mathscr \#1}\\

\\ \def\N{\mathbb N}\\

\\ \def\B{\mathbf{B}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\Z{\mathbb Z}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\Q{\mathbb Q}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\R{\mathbb R}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\C{\mathbb C}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\F{\mathbb F}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\A{\mathbb A}\\

\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\

\\ \def\X{\mathbb X}\\

\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\

\\ \def\E{\mathbb E}\\

\\ \def\O{\mathbb O}\\

\\ \def\U{\mathcal U}\\

\\ \def\pow{\mathcal P}\\

\\ \def\inv{^{-1}}\\

\\ \def\nrml{\triangleleft}\\

\\ \def\st{:}\\

\\ \def\\{\widetilde}\\

\\ \def\rem{\mathcal R}\\

\\ \def\sigalg{\$\sigma\$-algebra }\\

\\ \def\Gal{\mbox{Gal}}\\

\\ \def\iff{\leftrightarrow}\\

\\ \def\Iff{\Leftrightarrow}\\

\\ \def\land{\wedge}\\

\\ \def\And{\bigwedge}\\

\\ \def\entry{\entry}\\

\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\

\\ \def\Vee{\bigvee}\\

\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\

\\ \def\imp{\rightarrow}\\

\\ \def\Imp{\Rightarrow}\\

\\ \def\Fi{\Leftarrow}\\

\\ \def\var{\mbox{var}}\\

\\ \def\Th{\mbox{Th}}\\

\\ \def\entry{\entry}\\

\\ \def\sat{\mbox{Sat}}\\

\\ \def\con{\mbox{Con}}\\

\\ \def\iffmodels{\bmodels\models}\\

\\ \def\dbland{\bigwedge \\\\\bigwedge}\\

\\ \def\dom{\mbox{dom}}\\

\\ \def\rng{\mbox{range}}\\

\\ \def\isom{\cong}\\

\\\DeclareMathOperator{\wgt}{wgt}\\

\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\

\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\

\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\

\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\

\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\

\\ \renewcommand{\v}{\vtx{above}{}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\

\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\

\\ \def\ansfilename{practice-answers}\\

\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\

\\ \renewcommand{\bar}{\overline}\\

\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\ \newcommand{\lt}{<}\\

\\ \newcommand{\gt}{>}\\

\\ \newcommand{\amp}{&}\\

\\ \newcommand{\hexbox}$$3$${

  \def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}

  \def\y{-\r\*#1-sin{30}\*\r\*#1}

  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;

  \draw (\x,\y) node{#3};

}\\

\\\renewcommand{\bar}{\overline}\\

\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\\newcommand{\lt}{\<}\\

\\\newcommand{\gt}{\>}\\

\\\newcommand{\amp}{&}\\

Mapmakers in the fictional land of Euleria have drawn the borders of the various dukedoms of the land. To make the map pretty, they wish to color each region. Adjacent regions must be colored differently, but it is perfectly fine to color two distant regions with the same color. What is the fewest colors the mapmakers can use and still accomplish this task?

\![image-112.svg$$(https://math.libretexts.org/@api/deki/files/12841/image-112.svg?revision=1&size=bestfit&width=313&height=309)

\![$$(https://math.libretexts.org/images/image-112.svg)

Perhaps the most famous graph theory problem is how to color maps.

*Given any map of countries, states, counties, etc., how many colors are needed to color each region on the map so that neighboring regions are colored differently?*

Actual map makers usually use around seven colors. For one thing, they require watery regions to be a specific color, and with a lot of colors it is easier to find a permissible coloring. We want to know whether there is a smaller palette that will work for any map.

How is this related to graph theory? Well, if we place a vertex in the center of each region (say in the capital of each state) and then connect two vertices if their states share a border, we get a graph. Coloring regions on the map corresponds to coloring the vertices of the graph. Since neighboring regions cannot be colored the same, our graph cannot have vertices colored the same when those vertices are adjacent.

In general, given any graph \\G\text{,}\\ a coloring of the vertices is called (not surprisingly) a vertex coloring . If the vertex coloring has the property that adjacent vertices are colored differently, then the coloring is called proper . Every graph has a proper vertex coloring. For example, you could color every vertex with a different color. But often you can do better. The smallest number of colors needed to get a proper vertex coloring is called the chromatic number of the graph, written \\\chi(G)\\.

Example \\\PageIndex{1}\\: chromatic numbers

Find the chromatic number of the graphs below.

\![image-113.svg$$(https://math.libretexts.org/@api/deki/files/12847/image-113.svg?revision=1&size=bestfit&width=133&height=115)\![image-114.svg$$(https://math.libretexts.org/@api/deki/files/12848/image-114.svg?revision=1&size=bestfit&width=132&height=106)\![image-115.svg$$(https://math.libretexts.org/@api/deki/files/12846/image-115.svg?revision=1&size=bestfit&width=197&height=109)

Solution

The graph on the left is \\K_6\text{.}\\ The only way to properly color the graph is to give every vertex a different color (since every vertex is adjacent to every other vertex). Thus the chromatic number is 6.

The middle graph can be properly colored with just 3 colors (Red, Blue, and Green). For example:

\![image-116.svg$$(https://math.libretexts.org/@api/deki/files/12849/image-116.svg?revision=1&size=bestfit&width=157&height=184)

\![$$(https://math.libretexts.org/images/image-116.svg)

There is no way to color it with just two colors, since there are three vertices mutually adjacent (i.e., a triangle). Thus the chromatic number is 3.

The graph on the right is just \\K\_{2,3}\text{.}\\ As with all bipartite graphs, this graph has chromatic number 2: color the vertices on the top row red and the vertices on the bottom row blue.

It appears that there is no limit to how large chromatic numbers can get. It should not come as a surprise that \\K_n\\ has chromatic number \\n\text{.}\\ So how could there possibly be an answer to the original map coloring question? If the chromatic number of graph can be arbitrarily large, then it seems like there would be no upper bound to the number of colors needed for any map. But there is.

The key observation is that while it is true that for any number \\n\text{,}\\ there is a graph with chromatic number \\n\text{,}\\ only some graphs arrive as representations of maps. If you convert a map to a graph, the edges between vertices correspond to borders between the countries. So you should be able to connect vertices in such a way where the edges do not cross. In other words, the graphs representing maps are all *planar*!

So the question is, what is the largest chromatic number of any planar graph? The answer is the best known theorem of graph theory:

Theorem \\\PageIndex{1}\\: The Four Color Theorem

If \\G\\ is a planar graph, then the chromatic number of \\G\\ is less than or equal to 4. Thus any map can be properly colored with 4 or fewer colors.

We will not prove this theorem. Really. Even though the theorem is easy to state and understand, the proof is not. In fact, there is currently no “easy” known proof of the theorem. The current best proof still requires powerful computers to check an *unavoidable set* of 633 *reducible configurations*. The idea is that every graph must contain one of these reducible configurations (this fact also needs to be checked by a computer) and that reducible configurations can, in fact, be colored in 4 or fewer colors.

Coloring in General

!

The math department plans to offer 10 classes next semester. Some classes cannot run at the same time (perhaps they are taught by the same professor, or are required for seniors).

| Class: | Conflicts with: |

|--------|-----------------|

| A | D I |

| B | D I J |

| C | E F I |

| D | A B F |

| E | H I |

| F | I |

| G | J |

| H | E I J |

| I | A B C E F H |

| J | B G H |

How many different time slots are needed to teach these classes (and which should be taught at the same time)? More importantly, how could we use graph coloring to answer this question?

Cartography is certainly not the only application of graph coloring. There are plenty of situations in which you might wish partition the objects in question so that related objects are not in the same set. For example, you might wish to store chemicals safely. To avoid explosions, certain pairs of chemicals should not be stored in the same room. By coloring a graph (with vertices representing chemicals and edges representing potential negative interactions), you can determine the smallest number of rooms needed to store the chemicals.

Here is a further example:

Example \\\PageIndex{3}\\

Radio stations broadcast their signal at certain frequencies. However, there are a limited number of frequencies to choose from, so nationwide many stations use the same frequency. This works because the stations are far enough apart that their signals will not interfere; no one radio could pick them up at the same time.

Suppose 10 new radio stations are to be set up in a currently unpopulated (by radio stations) region. The radio stations that are close enough to each other to cause interference are recorded in the table below. What is the fewest number of frequencies the stations could use.

\![image-117.svg$$(https://math.libretexts.org/@api/deki/files/12843/image-117.svg?revision=1&size=bestfit&width=667&height=301)

Solution

Represent the problem as a graph with vertices as the stations and edges when two stations are close enough to cause interference. We are looking for the chromatic number of the graph. Vertices that are colored identically represent stations that can have the same frequency.

\![image-118.svg$$(https://math.libretexts.org/@api/deki/files/12844/image-118.svg?revision=1&size=bestfit&width=248&height=207)\![image-119.svg$$(https://math.libretexts.org/@api/deki/files/12845/image-119.svg?revision=1&size=bestfit&width=212&height=225)

This graph has chromatic number 5. A proper 5-coloring is shown on the right. Notice that the graph contains a copy of the complete graph \\K_5\\ so no fewer than 5 colors can be used.

\![$$(https://math.libretexts.org/images/image-118.svg) \![$$(https://math.libretexts.org/images/image-119.svg)

In the example above, the chromatic number was 5, but this is not a counterexample to the Four Color Theorem, since the graph representing the radio stations is not planar. It would be nice to have some quick way to find the chromatic number of a (possibly non-planar) graph. It turns out nobody knows whether an efficient algorithm for computing chromatic numbers exists.

While we might not be able to find the exact chromatic number of graph easily, we can often give a reasonable range for the chromatic number. In other words, we can give upper and lower bounds for chromatic number.

This is actually not very difficult: for every graph \\G\text{,}\\ the chromatic number of \\G\\ is at least 1 and at most the number of vertices of \\G\text{.}\\

What? You want *better* bounds on the chromatic number? Well you are in luck.

A clique in a graph is a set of vertices all of which are pairwise adjacent. In other words, a clique of size \\n\\ is just a copy of the complete graph \\K_n\text{.}\\ We define the clique number of a graph to be the largest \\n\\ for which the graph contains a clique of size \\n\text{.}\\ Any clique of size \\n\\ cannot be colored with fewer than \\n\\ colors, so we have a nice lower bound:

Theorem \\\PageIndex{2}\\

The chromatic number of a graph \\G\\ is at least the clique number of \\G\text{.}\\

There are times when the chromatic number of \\G\\ is *equal* to the clique number. These graphs have a special name; they are called perfect . If you know that a graph is perfect, then finding the chromatic number is simply a matter of searching for the largest clique.⁴There are special classes of graphs which can be proved to be perfect. One such class is the set of chordal graphs, which have the property that every cycle in the graph contains a chord —an edge between two vertices in of the cycle which are not adjacent in the cycle. However, not all graphs are perfect.

For an upper bound, we can improve on “the number of vertices” by looking to the degrees of vertices. Let \\\Delta(G)\\ be the largest degree of any vertex in the graph \\G\text{.}\\ One reasonable guess for an upper bound on the chromatic number is \\\chi(G) \le \Delta(G) + 1\text{.}\\ Why is this reasonable? Starting with any vertex, it together with all of its neighbors can always be colored in \\\Delta(G) + 1\\ colors, since at most we are talking about \\\Delta(G) + 1\\ vertices in this set. Now fan out! At any point, if you consider an already colored vertex, some of its neighbors might be colored, some might not. But no matter what, that vertex and its neighbors could all be colored distinctly, since there are at most \\\Delta(G)\\ neighbors, plus the one vertex being considered.

In fact, there are examples of graphs for which \\\chi(G) = \Delta(G) + 1\text{.}\\ For any \\n\text{,}\\ the complete graph \\K_n\\ has chromatic number \\n\text{,}\\ but \\\Delta(K_n) = n-1\\ (since every vertex is adjacent to every *other* vertex). Additionally, any *odd* cycle will have chromatic number 3, but the degree of every vertex in a cycle is 2. It turns out that these are the only two types of examples where we get equality, a result known as Brooks' Theorem.

Theorem \\\PageIndex{3}\\: Brooks' Theorem

Any graph \\G\\ satisfies \\\chi(G) \le \Delta(G)\text{,}\\ unless \\G\\ is a complete graph or an odd cycle, in which case \\\chi(G) = \Delta(G) + 1\text{.}\\

The proof of this theorem is *just* complicated enough that we will not present it here (although you are asked to prove a special case in the exercises). The adventurous reader is encouraged to find a book on graph theory for suggestions on how to prove the theorem.

Coloring Edges

The chromatic number of a graph tells us about coloring vertices, but we could also ask about coloring edges. Just like with vertex coloring, we might insist that edges that are adjacent must be colored differently. Here, we are thinking of two edges as being adjacent if they are incident to the same vertex. The least number of colors required to properly color the edges of a graph \\G\\ is called the chromatic index of \\G\text{,}\\ written \\\chi'(G)\\.

Example \\\PageIndex{3}\\

Six friends decide to spend the afternoon playing chess. Everyone will play everyone else once. They have plenty of chess sets but nobody wants to play more than one game at a time. Games will last an hour (thanks to their handy chess clocks). How many hours will the tournament last?

Solution

Represent each player with a vertex and put an edge between two players if they will play each other. In this case, we get the graph \\K_6\text{:}\\

\![image-120.svg$$(https://math.libretexts.org/@api/deki/files/12842/image-120.svg?revision=1&size=bestfit&width=213&height=184)

\![$$(https://math.libretexts.org/images/image-120.svg)

We must color the edges; each color represents a different hour. Since different edges incident to the same vertex will be colored differently, no player will be playing two different games (edges) at the same time. Thus we need to know the chromatic index of \\K_6\text{.}\\

Notice that for sure \\\chi'(K_6) \ge 5\text{,}\\ since there is a vertex of degree 5. It turns out 5 colors is enough (go find such a coloring). Therefore the friends will play for 5 hours.

Interestingly, if one of the friends in the above example left, the remaining 5 chess-letes would still need 5 hours: the chromatic index of \\K_5\\ is also 5.

In general, what can we say about chromatic index? Certainly \\\chi'(G) \ge \Delta(G)\text{.}\\ But how much higher could it be? Only a little higher.

Theorem \\\PageIndex{4}\\: Vizing's Theorem

For any graph \\G\text{,}\\ the chromatic index \\\chi'(G)\\ is either \\\Delta(G)\\ or \\\Delta(G) + 1\\.

At first this theorem makes it seem like chromatic index might not be very interesting. However, deciding which case a graph is in is not always easy. Graphs for which \\\chi'(G) = \Delta(G)\\ are called *class 1*, while the others are called *class 2*. Bipartite graphs always satisfy \\\chi'(G) = \Delta(G)\text{,}\\ so are class 1 (this was proved by König in 1916, decades before Vizing proved his theorem in 1964). In 1965 Vizing proved that all planar graphs with \\\Delta(G) \ge 8\\ are of class 1, but this does not hold for all planar graphs with \\2 \le \Delta(G) \le 5\text{.}\\ Vizing conjectured that all planar graphs with \\\Delta(G) = 6\\ or \\\Delta(G) = 7\\ are class 1; the \\\Delta(G) = 7\\ case was proved in 2001 by Sanders and Zhao; the \\\Delta(G) = 6\\ case is still open.

There is another interesting way we might consider coloring edges, quite different from what we have discussed so far. What if we colored every edge of a graph either red or blue. Can we do so without, say, creating a *monochromatic* triangle (i.e., an all red or all blue triangle)? Certainly for some graphs the answer is yes. Try doing so for \\K_4\text{.}\\ What about \\K_5\text{?}\\ \\K_6\text{?}\\ How far can we go?

The answer to the above problem is known and is a fun problem to do as an exercise. We could extend the question in a variety of ways. What if we had three colors? What if we were trying to avoid other graphs. The surprising fact is that very little is known about these questions. For example, we know that you need to go up to \\K\_{17}\\ in order to force a monochromatic triangle using three colors, but nobody knows how big you need to go with more colors. Similarly, we know that using two colors \\K\_{18}\\ is the smallest graph that forces a monochromatic copy of \\K_4\text{,}\\ but the best we have to force a monochromatic \\K\_{5}\\ is a range, somewhere from \\K\_{43}\\ to \\K\_{49}\text{.}\\ If you are interested in these sorts of questions, this area of graph theory is called Ramsey theory. Check it out.

---

4_4_3A_Euler_Paths_and_Circuits

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/4%3A_Graph_Theory/4.4%3A_Euler_Paths_and_Circuits

Skip to main content

\\ \def\d{\displaystyle}\\

\\ \newcommand{\f}$$1$${\mathfrak \#1}\\

\\ \newcommand{\s}$$1$${\mathscr \#1}\\

\\ \def\N{\mathbb N}\\

\\ \def\B{\mathbf{B}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\Z{\mathbb Z}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\Q{\mathbb Q}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\R{\mathbb R}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\C{\mathbb C}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\F{\mathbb F}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\A{\mathbb A}\\

\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\

\\ \def\X{\mathbb X}\\

\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\

\\ \def\E{\mathbb E}\\

\\ \def\O{\mathbb O}\\

\\ \def\U{\mathcal U}\\

\\ \def\pow{\mathcal P}\\

\\ \def\inv{^{-1}}\\

\\ \def\nrml{\triangleleft}\\

\\ \def\st{:}\\

\\ \def\\{\widetilde}\\

\\ \def\rem{\mathcal R}\\

\\ \def\sigalg{\$\sigma\$-algebra }\\

\\ \def\Gal{\mbox{Gal}}\\

\\ \def\iff{\leftrightarrow}\\

\\ \def\Iff{\Leftrightarrow}\\

\\ \def\land{\wedge}\\

\\ \def\And{\bigwedge}\\

\\ \def\entry{\entry}\\

\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\

\\ \def\Vee{\bigvee}\\

\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\

\\ \def\imp{\rightarrow}\\

\\ \def\Imp{\Rightarrow}\\

\\ \def\Fi{\Leftarrow}\\

\\ \def\var{\mbox{var}}\\

\\ \def\Th{\mbox{Th}}\\

\\ \def\entry{\entry}\\

\\ \def\sat{\mbox{Sat}}\\

\\ \def\con{\mbox{Con}}\\

\\ \def\iffmodels{\bmodels\models}\\

\\ \def\dbland{\bigwedge \\\\\bigwedge}\\

\\ \def\dom{\mbox{dom}}\\

\\ \def\rng{\mbox{range}}\\

\\ \def\isom{\cong}\\

\\\DeclareMathOperator{\wgt}{wgt}\\

\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\

\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\

\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\

\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\

\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\

\\ \renewcommand{\v}{\vtx{above}{}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\

\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\

\\ \def\ansfilename{practice-answers}\\

\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\

\\ \renewcommand{\bar}{\overline}\\

\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\ \newcommand{\lt}{<}\\

\\ \newcommand{\gt}{>}\\

\\ \newcommand{\amp}{&}\\

\\ \newcommand{\hexbox}$$3$${

  \def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}

  \def\y{-\r\*#1-sin{30}\*\r\*#1}

  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;

  \draw (\x,\y) node{#3};

}\\

\\\renewcommand{\bar}{\overline}\\

\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\\newcommand{\lt}{\<}\\

\\\newcommand{\gt}{\>}\\

\\\newcommand{\amp}{&}\\

Investigate!

An Euler path , in a graph or multigraph, is a walk through the graph which uses every edge exactly once. An Euler circuit is an Euler path which starts and stops at the same vertex. Our goal is to find a quick way to check whether a graph (or multigraph) has an Euler path or circuit.

1. Which of the graphs below have Euler paths? Which have Euler circuits?

\![image-129.svg$$(https://math.libretexts.org/@api/deki/files/12877/image-129.svg?revision=1&size=bestfit&width=121&height=175) \![image-130.svg$$(https://math.libretexts.org/@api/deki/files/12878/image-130.svg?revision=1&size=bestfit&width=117&height=117) \![image-131.svg$$(https://math.libretexts.org/@api/deki/files/12879/image-131.svg?revision=1&size=bestfit&width=219&height=114) \![image-132.svg$$(https://math.libretexts.org/@api/deki/files/12880/image-132.svg?revision=1&size=bestfit&width=144&height=118)

\![$$(https://math.libretexts.org/images/image-129.svg) \![$$(https://math.libretexts.org/images/image-130.svg) \![$$(https://math.libretexts.org/images/image-131.svg) \![$$(https://math.libretexts.org/images/image-132.svg)

2. List the degrees of each vertex of the graphs above. Is there a connection between degrees and the existence of Euler paths and circuits?

3. Is it possible for a graph with a degree 1 vertex to have an Euler circuit? If so, draw one. If not, explain why not. What about an Euler path?

4. What if every vertex of the graph has degree 2. Is there an Euler path? An Euler circuit? Draw some graphs.

5. Below is *part* of a graph. Even though you can only see some of the vertices, can you deduce whether the graph will have an Euler path or circuit?

​​​​​​​\![image-133.svg$$(https://math.libretexts.org/@api/deki/files/12881/image-133.svg?revision=1&size=bestfit&width=325&height=112)

1. \![$$(https://math.libretexts.org/images/image-133.svg)

If we start at a vertex and trace along edges to get to other vertices, we create a *walk* through the graph. More precisely, a walk in a graph is a sequence of vertices such that every vertex in the sequence is adjacent to the vertices before and after it in the sequence. If the walk travels along every edge exactly once, then the walk is called an Euler path (or Euler walk ). If, in addition, the starting and ending vertices are the same (so you trace along every edge exactly once and end up where you started), then the walk is called an Euler circuit (or Euler tour ). Of course if a graph is not connected, there is no hope of finding such a path or circuit. For the rest of this section, assume all the graphs discussed are connected.

The bridges of Königsberg problem is really a question about the existence of Euler paths. There will be a route that crosses every bridge exactly once if and only if the graph below has an Euler path:

\![image-134.svg$$(https://math.libretexts.org/@api/deki/files/12882/image-134.svg?revision=1&size=bestfit&width=157&height=141)

\![$$(https://math.libretexts.org/images/image-134.svg)

This graph is small enough that we could actually check every possible walk that does not reuse edges, and in doing so convince ourselves that there is no Euler path (let alone an Euler circuit). On small graphs which do have an Euler path, it is usually not difficult to find one. Our goal is to find a quick way to check whether a graph has an Euler path or circuit, even if the graph is quite large.

One way to guarantee that a graph does *not* have an Euler circuit is to include a “spike,” a vertex of degree 1.

\![image-135.svg$$(https://math.libretexts.org/@api/deki/files/12883/image-135.svg?revision=1&size=bestfit&width=168&height=78)

\![$$(https://math.libretexts.org/images/image-135.svg)

The vertex \\a\\ has degree 1, and if you try to make an Euler circuit, you see that you will get stuck at the vertex. It is a dead end. That is, unless you start there. But then there is no way to return, so there is no hope of finding an Euler circuit. There is however an Euler path. It starts at the vertex \\a\text{,}\\ then loops around the triangle. You will end at the vertex of degree 3.

You run into a similar problem whenever you have a vertex of any odd degree. If you start at such a vertex, you will not be able to end there (after traversing every edge exactly once). After using one edge to leave the starting vertex, you will be left with an even number of edges emanating from the vertex. Half of these could be used for returning to the vertex, the other half for leaving. So you return, then leave. Return, then leave. The only way to use up all the edges is to use the last one by leaving the vertex. On the other hand, if you have a vertex with odd degree that you do not start a path at, then you will eventually get stuck at that vertex. The path will use pairs of edges incident to the vertex to arrive and leave again. Eventually all but one of these edges will be used up, leaving only an edge to arrive by, and none to leave again.

What all this says is that if a graph has an Euler path and two vertices with odd degree, then the Euler path must start at one of the odd degree vertices and end at the other. In such a situation, every other vertex *must* have an even degree since we need an equal number of edges to get to those vertices as to leave them. How could we have an Euler circuit? The graph could not have any odd degree vertex as an Euler path would have to start there or end there, but not both. Thus for a graph to have an Euler circuit, all vertices must have even degree.

The converse is also true: if all the vertices of a graph have even degree, then the graph has an Euler circuit, and if there are exactly two vertices with odd degree, the graph has an Euler path. To prove this is a little tricky, but the basic idea is that you will never get stuck because there is an “outbound” edge for every “inbound” edge at every vertex. If you try to make an Euler path and miss some edges, you will always be able to “splice in” a circuit using the edges you previously missed.

Euler Paths and Circuits

• A graph has an Euler circuit if and only if the degree of every vertex is even.
• A graph has an Euler path if and only if there are at most two vertices with odd degree.

Since the bridges of Königsberg graph has all four vertices with odd degree, there is no Euler path through the graph. Thus there is no way for the townspeople to cross every bridge exactly once.

Hamilton Paths

Suppose you wanted to tour Königsberg in such a way where you visit each land mass (the two islands and both banks) exactly once. This can be done. In graph theory terms, we are asking whether there is a path which visits every vertex exactly once. Such a path is called a Hamilton path (or Hamiltonian path ). We could also consider Hamilton cycles , which are Hamliton paths which start and stop at the same vertex.

Example \\\PageIndex{1}\\

Determine whether the graphs below have a Hamilton path.

\![image-136.svg$$(https://math.libretexts.org/@api/deki/files/12885/image-136.svg?revision=1&size=bestfit&width=159&height=151) \![image-137.svg$$(https://math.libretexts.org/@api/deki/files/12884/image-137.svg?revision=1&size=bestfit&width=162&height=154)

Solution

The graph on the left has a Hamilton path (many different ones, actually), as shown here:

\![image-138.svg$$(https://math.libretexts.org/@api/deki/files/12886/image-138.svg?revision=1&size=bestfit&width=133&height=126)

\![$$(https://math.libretexts.org/images/image-138.svg)

The graph on the right does not have a Hamilton path. You would need to visit each of the “outside” vertices, but as soon as you visit one, you get stuck. Note that this graph does not have an Euler path, although there are graphs with Euler paths but no Hamilton paths.

\![$$(https://math.libretexts.org/images/image-136.svg)

\![$$(https://math.libretexts.org/images/image-137.svg)

It appears that finding Hamilton paths would be easier because graphs often have more edges than vertices, so there are fewer requirements to be met. However, nobody knows whether this is true. There is no known simple test for whether a graph has a Hamilton path. For small graphs this is not a problem, but as the size of the graph grows, it gets harder and harder to check wither there is a Hamilton path. In fact, this is an example of a question which as far as we know is too difficult for computers to solve; it is an example of a problem which is NP-complete.

---

4_5_3A_Matching_in_Bipartite_Graphs

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/4%3A_Graph_Theory/4.5%3A_Matching_in_Bipartite_Graphs

Skip to main content

\\ \def\d{\displaystyle}\\

\\ \newcommand{\f}$$1$${\mathfrak \#1}\\

\\ \newcommand{\s}$$1$${\mathscr \#1}\\

\\ \def\N{\mathbb N}\\

\\ \def\B{\mathbf{B}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\Z{\mathbb Z}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\Q{\mathbb Q}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\R{\mathbb R}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\C{\mathbb C}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\F{\mathbb F}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\A{\mathbb A}\\

\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\

\\ \def\X{\mathbb X}\\

\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\

\\ \def\E{\mathbb E}\\

\\ \def\O{\mathbb O}\\

\\ \def\U{\mathcal U}\\

\\ \def\pow{\mathcal P}\\

\\ \def\inv{^{-1}}\\

\\ \def\nrml{\triangleleft}\\

\\ \def\st{:}\\

\\ \def\\{\widetilde}\\

\\ \def\rem{\mathcal R}\\

\\ \def\sigalg{\$\sigma\$-algebra }\\

\\ \def\Gal{\mbox{Gal}}\\

\\ \def\iff{\leftrightarrow}\\

\\ \def\Iff{\Leftrightarrow}\\

\\ \def\land{\wedge}\\

\\ \def\And{\bigwedge}\\

\\ \def\entry{\entry}\\

\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\

\\ \def\Vee{\bigvee}\\

\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\

\\ \def\imp{\rightarrow}\\

\\ \def\Imp{\Rightarrow}\\

\\ \def\Fi{\Leftarrow}\\

\\ \def\var{\mbox{var}}\\

\\ \def\Th{\mbox{Th}}\\

\\ \def\entry{\entry}\\

\\ \def\sat{\mbox{Sat}}\\

\\ \def\con{\mbox{Con}}\\

\\ \def\iffmodels{\bmodels\models}\\

\\ \def\dbland{\bigwedge \\\\\bigwedge}\\

\\ \def\dom{\mbox{dom}}\\

\\ \def\rng{\mbox{range}}\\

\\ \def\isom{\cong}\\

\\\DeclareMathOperator{\wgt}{wgt}\\

\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\

\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\

\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\

\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\

\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\

\\ \renewcommand{\v}{\vtx{above}{}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\

\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\

\\ \def\ansfilename{practice-answers}\\

\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\

\\ \renewcommand{\bar}{\overline}\\

\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\ \newcommand{\lt}{<}\\

\\ \newcommand{\gt}{>}\\

\\ \newcommand{\amp}{&}\\

\\ \newcommand{\hexbox}$$3$${

  \def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}

  \def\y{-\r\*#1-sin{30}\*\r\*#1}

  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;

  \draw (\x,\y) node{#3};

}\\

\\\renewcommand{\bar}{\overline}\\

\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\\newcommand{\lt}{\<}\\

\\\newcommand{\gt}{\>}\\

\\\newcommand{\amp}{&}\\

Investigate!

Given a bipartite graph, a matching is a subset of the edges for which every vertex belongs to exactly one of the edges. Our goal in this activity is to discover some criterion for when a bipartite graph has a matching.

Does the graph below contain a matching? If so, find one.

\![image-145.svg$$(https://math.libretexts.org/@api/deki/files/12934/image-145.svg?revision=1&size=bestfit&width=317&height=132)

\![$$(https://math.libretexts.org/images/image-145.svg)

Not all bipartite graphs have matchings. Draw as many fundamentally different examples of bipartite graphs which do NOT have matchings. Your goal is to find all the possible obstructions to a graph having a perfect matching. Write down the *necessary* conditions for a graph to have a matching (that is, fill in the blank: If a graph has a matching, then ). Then ask yourself whether these conditions are sufficient (is it true that if , then the graph has a matching?).

We conclude with one more example of a graph theory problem to illustrate the variety and vastness of the subject.

Suppose you have a bipartite graph \\G\text{.}\\ This will consist of two sets of vertices \\A\\ and \\B\\ with some edges connecting some vertices of \\A\\ to some vertices in \\B\\ (but of course, no edges between two vertices both in \\A\\ or both in \\B\$. A matching of \\A\\ is a subset of the edges for which each vertex of \\A\\ belongs to exactly one edge of the subset, and no vertex in \\B\\ belongs to more than one edge in the subset. In practice we will assume that \\\|A\| = \|B\|\\ (the two sets have the same number of vertices) so this says that every vertex in the graph belongs to exactly one edge in the matching.⁵Note: what we are calling a *matching* is sometimes called a *perfect matching* or *complete matching*. This is because in it interesting to look at non-perfect matchings as well. We will call those *partial* matchings.

Some context might make this easier to understand. Think of the vertices in \\A\\ as representing students in a class, and the vertices in \\B\\ as representing presentation topics. We put an edge from a vertex \\a \in A\\ to a vertex \\b \in B\\ if student \\a\\ would like to present on topic \\b\text{.}\\ Of course, some students would want to present on more than one topic, so their vertex would have degree greater than 1. As the teacher, you want to assign each student their own unique topic. Thus you want to find a matching of \\A\text{:}\\ you pick some subset of the edges so that each student gets matched up with exactly one topic, and no topic gets matched to two students.⁶The standard example for matchings used to be the *marriage problem* in which \\A\\ consisted of the men in the town, \\B\\ the women, and an edge represented a marriage that was agreeable to both parties. A matching then represented a way for the town elders to marry off everyone in the town, no polygamy allowed. We have chosen a more progressive context for the sake of political correctness.

The question is: when does a bipartite graph contain a matching of \\A\text{?}\\ To begin to answer this question, consider what could prevent the graph from containing a matching. This will not necessarily tell us a condition when the graph *does* have a matching, but at least it is a start.

One way \\G\\ could not have a matching is if there is a vertex in \\A\\ not adjacent to any vertex in \\B\\ (so having degree 0). What else? What if two students both like the same one topic, and no others? Then after assigning that one topic to the first student, there is nothing left for the second student to like, so it is very much as if the second student has degree 0. Or what if three students like only two topics between them. Again, after assigning one student a topic, we reduce this down to the previous case of two students liking only one topic. We can continue this way with more and more students.

It should be clear at this point that if there is every a group of \\n\\ students who as a group like \\n-1\\ or fewer topics, then no matching is possible. This is true for any value of \\n\text{,}\\ and any group of \\n\\ students.

To make this more graph-theoretic, say you have a set \\S \subseteq A\\ of vertices. Define \\N(S)\\ to be the set of all the neighbors of vertices in \\S\text{.}\\ That is, \\N(S)\\ contains all the vertices (in \\B\$ which are adjacent to at least one of the vertices in \\S\text{.}\\ (In the student/topic graph, \\N(S)\\ is the set of topics liked by the students of \\S\text{.}\$ Our discussion above can be summarized as follows:

Matching Condition

If a bipartite graph \\G = \\A, B\\\\ has a matching of \\A\text{,}\\ then

\begin{equation\*} \|N(S)\| \ge \|S\| \end{equation\*}

for all \\S \subseteq A\text{.}\\

Is the converse true? Suppose \\G\\ satisfies the matching condition \\\|N(S)\| \ge \|S\|\\ for all \\S \subseteq A\\ (every set of vertices has at least as many neighbors than vertices in the set). Does that mean that there is a matching? Surprisingly, yes. The obvious necessary condition is also sufficient.⁷This happens often in graph theory. If you can avoid the obvious counterexamples, you often get what you want. This is a theorem first proved by Philip Hall in 1935.⁸There is also an infinite version of the theorem which was proved by Marshal Hall, Jr. The name is a coincidence though as the two Halls are not related.

Theorem4.5.1Hall's Marriage Theorem

Let \\G\\ be a bipartite graph with sets \\A\\ and \\B\text{.}\\ Then \\G\\ has a matching of \\A\\ if and only if

\begin{equation\*} \|N(S)\| \ge \|S\| \end{equation\*}

for all \\S \subseteq A\text{.}\\

There are quite a few different proofs of this theorem – a quick internet search will get you started.

In addition to its application to marriage and student presentation topics, matchings have applications all over the place. We conclude with one such example.

Example \\\PageIndex{1}\\

Suppose you deal 52 regular playing cards into 13 piles of 4 cards each. Prove that you can always select one card from each pile to get one of each of the 13 card values Ace, 2, 3, …, 10, Jack, Queen, and King.

Solution

Doing this directly would be difficult, but we can use the matching condition to help. Construct a graph \\G\\ with 13 vertices in the set \\A\text{,}\\ each representing one of the 13 card values, and 13 vertices in the set \\B\text{,}\\ each representing one of the 13 piles. Draw an edge between a vertex \\a \in A\\ to a vertex \\b \in B\\ if a card with value \\a\\ is in the pile \\b\text{.}\\ Notice that we are just looking for a matching of \\A\text{;}\\ each value needs to be found in the piles exactly once.

We will have a matching if the matching condition holds. Given any set of card values (a set \\S \subseteq A\$ we must show that \\\|N(S)\| \ge \|S\|\text{.}\\ That is, the number of piles that contain those values is at least the number of different values. But what if it wasn't? Say \\\|S\| = k\text{.}\\ If \\\|N(S)\| \< k\text{,}\\ then we would have fewer than \\4k\\ different cards in those piles (since each pile contains 4 cards). But there are \\4k\\ cards with the \\k\\ different values, so at least one of these cards must be in another pile, a contradiction. Thus the matching condition holds, so there is a matching, as required.

---

4_E_3A_Graph_Theory__Exercises_

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/4%3A_Graph_Theory/4.E%3A_Graph_Theory_(Exercises)

Skip to main content

\\ \def\d{\displaystyle}\\

\\ \newcommand{\f}$$1$${\mathfrak \#1}\\

\\ \newcommand{\s}$$1$${\mathscr \#1}\\

\\ \def\N{\mathbb N}\\

\\ \def\B{\mathbf{B}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\Z{\mathbb Z}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\Q{\mathbb Q}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\R{\mathbb R}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\C{\mathbb C}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\F{\mathbb F}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\A{\mathbb A}\\

\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\

\\ \def\X{\mathbb X}\\

\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\

\\ \def\E{\mathbb E}\\

\\ \def\O{\mathbb O}\\

\\ \def\U{\mathcal U}\\

\\ \def\pow{\mathcal P}\\

\\ \def\inv{^{-1}}\\

\\ \def\nrml{\triangleleft}\\

\\ \def\st{:}\\

\\ \def\\{\widetilde}\\

\\ \def\rem{\mathcal R}\\

\\ \def\sigalg{\$\sigma\$-algebra }\\

\\ \def\Gal{\mbox{Gal}}\\

\\ \def\iff{\leftrightarrow}\\

\\ \def\Iff{\Leftrightarrow}\\

\\ \def\land{\wedge}\\

\\ \def\And{\bigwedge}\\

\\ \def\entry{\entry}\\

\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\

\\ \def\Vee{\bigvee}\\

\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\

\\ \def\imp{\rightarrow}\\

\\ \def\Imp{\Rightarrow}\\

\\ \def\Fi{\Leftarrow}\\

\\ \def\var{\mbox{var}}\\

\\ \def\Th{\mbox{Th}}\\

\\ \def\entry{\entry}\\

\\ \def\sat{\mbox{Sat}}\\

\\ \def\con{\mbox{Con}}\\

\\ \def\iffmodels{\bmodels\models}\\

\\ \def\dbland{\bigwedge \\\\\bigwedge}\\

\\ \def\dom{\mbox{dom}}\\

\\ \def\rng{\mbox{range}}\\

\\ \def\isom{\cong}\\

\\\DeclareMathOperator{\wgt}{wgt}\\

\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\

\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\

\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\

\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\

\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\

\\ \renewcommand{\v}{\vtx{above}{}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\

\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\

\\ \def\ansfilename{practice-answers}\\

\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\

\\ \renewcommand{\bar}{\overline}\\

\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\ \newcommand{\lt}{<}\\

\\ \newcommand{\gt}{>}\\

\\ \newcommand{\amp}{&}\\

\\ \newcommand{\hexbox}$$3$${

  \def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}

  \def\y{-\r\*#1-sin{30}\*\r\*#1}

  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;

  \draw (\x,\y) node{#3};

}\\

\\\renewcommand{\bar}{\overline}\\

\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\\newcommand{\lt}{\<}\\

\\\newcommand{\gt}{\>}\\

\\\newcommand{\amp}{&}\\

4.1: Definitions

1

If 10 people each shake hands with each other, how many handshakes took place? What does this question have to do with graph theory?

Answer

This is asking for the number of edges in \\K\_{10}\text{.}\\ Each vertex (person) has degree (shook hands with) 9 (people). So the sum of the degrees is \\90\text{.}\\ However, the degrees count each edge (handshake) twice, so there are 45 edges in the graph. That is how many handshakes took place.

2

Among a group of 5 people, is it possible for everyone to be friends with exactly 2 of the people in the group? What about 3 of the people in the group?

Answer

It is possible for everyone to be friends with exactly 2 people. You could arrange the 5 people in a circle and say that everyone is friends with the two people on either side of them (so you get the graph \\C_5\$. However, it is not possible for everyone to be friends with 3 people. That would lead to a graph with an odd number of odd degree vertices which is impossible since the sum of the degrees must be even.

3

Is it possible for two *different* (non-isomorphic) graphs to have the same number of vertices and the same number of edges? What if the degrees of the vertices in the two graphs are the same (so both graphs have vertices with degrees 1, 2, 2, 3, and 4, for example)? Draw two such graphs or explain why not.

Answer

Yes. For example, both graphs below contain 6 vertices, 7 edges, and have degrees (2,2,2,2,3,3).

\![image-88.svg$$(https://math.libretexts.org/@api/deki/files/12938/image-88.svg?revision=1&size=bestfit&width=216&height=59) \![image-89.svg$$(https://math.libretexts.org/@api/deki/files/12939/image-89.svg?revision=1&size=bestfit&width=109&height=94)

\![$$(https://math.libretexts.org/images/image-88.svg) \![$$(https://math.libretexts.org/images/image-89.svg)

4

Are the two graphs below equal? Are they isomorphic? If they are isomorphic, give the isomorphism. If not, explain.

• Graph 1: \\V = \\a,b,c,d,e\\\text{,}\\ \\E = \\\\a,b\\, \\a,c\\, \\a,e\\, \\b,d\\, \\b,e\\, \\c,d\\\\\text{.}\\
• Graph 2:

\![image-90.svg$$(https://math.libretexts.org/@api/deki/files/12940/image-90.svg?revision=1&size=bestfit&width=138&height=99)

\![$$(https://math.libretexts.org/images/image-90.svg)

Answer

The graphs are not equal. For example, graph 1 has an edge \\\\a,b\\\\ but graph 2 does not have that edge. They are isomorphic. One possible isomorphism is \\f:G_1 \to G_2\\ defined by \\f(a) = d\text{,}\\ \\f(b) = c\text{,}\\ \\f(c) = e\text{,}\\ \\f(d) = b\text{,}\\ \\f(e) = a\text{.}\\

5

Consider the following two graphs:

\\G_1\\

• \\V_1=\\a,b,c,d,e,f,g\\\\
• \\E_1=\\\\a,b\\,\\a,d\\,\\b,c\\,\\b,d\\,\\b,e\\,\\b,f\\,\\c,g\\,\\d,e\\,\\
• \\\\e,f\\,\\f,g\\\\\text{.}\\

\\G_2\\

• \\V_2=\\v_1,v_2,v_3,v_4,v_5,v_6,v_7\\\text{,}\\
• \\E_2=\\\\v_1,v_4\\,\\v_1,v_5\\,\\v_1,v_7\\,\\v_2,v_3\\,\\v_2,v_6\\,\\
• \\\\v_3,v_5\\,\\v_3,v_7\\,\\v_4,v_5\\,\\v_5,v_6\\,\\v_5,v_7\\\\\\

1. Let \\f:G_1 \rightarrow G_2\\ be a function that takes the vertices of Graph 1 to vertices of Graph 2. The function is given by the following table:

| | | | | | | | |

|----------|---------|---------|---------|---------|---------|---------|---------|

| \\x\\ | \\a\\ | \\b\\ | \\c\\ | \\d\\ | \\e\\ | \\f\\ | \\g\\ |

| \\f(x)\\ | \\v_4\\ | \\v_5\\ | \\v_1\\ | \\v_6\\ | \\v_2\\ | \\v_3\\ | \\v_7\\ |

Does \\f\\ define an isomorphism between Graph 1 and Graph 2? Explain.

2. Define a new function \\g\\ (with \\g\not=f\$ that defines an isomorphism between Graph 1 and Graph 2.

3. Is the graph pictured below isomorphic to Graph 1 and Graph 2? Explain.

\![image-91.svg$$(https://math.libretexts.org/@api/deki/files/12941/image-91.svg?revision=1&size=bestfit&width=188&height=99)

\![$$(https://math.libretexts.org/images/image-91.svg)

6

Which of the graphs below are bipartite? Justify your answers.

\![image-92.svg$$(https://math.libretexts.org/@api/deki/files/12942/image-92.svg?revision=1&size=bestfit&width=133&height=131) \![image-93.svg$$(https://math.libretexts.org/@api/deki/files/12943/image-93.svg?revision=1&size=bestfit&width=136&height=118) \![image-94.svg$$(https://math.libretexts.org/@api/deki/files/12944/image-94.svg?revision=1&size=bestfit&width=110&height=112) \![image-95.svg$$(https://math.libretexts.org/@api/deki/files/12945/image-95.svg?revision=1&size=bestfit&width=140&height=136)

\![$$(https://math.libretexts.org/images/image-92.svg) \![$$(https://math.libretexts.org/images/image-93.svg) \![$$(https://math.libretexts.org/images/image-94.svg) \![$$(https://math.libretexts.org/images/image-95.svg)

Answer

Three of the graphs are bipartite. The one which is not is \\C_7\\ (second from the right). To see that the three graphs are bipartite, we can just give the bipartition into two sets \\A\\ and \\B\text{,}\\ as labeled below:

\![image-96.svg$$(https://math.libretexts.org/@api/deki/files/12946/image-96.svg?revision=1&size=bestfit&width=136&height=155) \![image-97.svg$$(https://math.libretexts.org/@api/deki/files/12947/image-97.svg?revision=1&size=bestfit&width=171&height=113) \![image-98.svg$$(https://math.libretexts.org/@api/deki/files/12948/image-98.svg?revision=1&size=bestfit&width=135&height=155)

\![$$(https://math.libretexts.org/images/image-96.svg) \![$$(https://math.libretexts.org/images/image-97.svg) \![$$(https://math.libretexts.org/images/image-98.svg)

The graph \\C_7\\ is not bipartite because it is an *odd* cycle. You would want to put every other vertex into the set \\A\text{,}\\ but if you travel clockwise in this fashion, the last vertex will also be put into the set \\A\text{,}\\ leaving two \\A\\ vertices adjacent (which makes it not a bipartition).

7

For which \\n \ge 3\\ is the graph \\C_n\\ bipartite?

8

For each of the following, try to give two *different* unlabeled graphs with the given properties, or explain why doing so is impossible.

1. Two different trees with the same number of vertices and the same number of edges. A tree is a connected graph with no cycles.

2. Two different graphs with 8 vertices all of degree 2.

3. Two different graphs with 5 vertices all of degree 4.

4. Two different graphs with 5 vertices all of degree 3.

Answer

1. \![$$(https://math.libretexts.org/images/image-100.svg)

1. For example:

\![image-99.svg$$(https://math.libretexts.org/@api/deki/files/12949/image-99.svg?revision=1) \![image-100.svg$$(https://math.libretexts.org/@api/deki/files/12950/image-100.svg?revision=1)

2. This is not possible if we require the graphs to be connected. If not, we could take \\C_8\\ as one graph and two copies of \\C_4\\ as the other.

3. Not possible. If you have a graph with 5 vertices all of degree 4, then every vertex must be adjacent to every other vertex. This is the graph \\K_5\text{.}\\

4. This is not possible. In fact, there is not even one graph with this property (such a graph would have \\5\cdot 3/2 = 7.5\\ edges).

4.2: Planar Graphs

1

Is it possible for a planar graph to have 6 vertices, 10 edges and 5 faces? Explain.

Answer

No. A (connected) planar graph must satisfy Euler's formula: \\v - e + f = 2\text{.}\\ Here \\v - e + f = 6 - 10 + 5 = 1\text{.}\\

2

The graph \\G\\ has 6 vertices with degrees \\2, 2, 3, 4, 4, 5\text{.}\\ How many edges does \\G\\ have? Could \\G\\ be planar? If so, how many faces would it have. If not, explain.

Answer

\\G\\ has 10 edges, since \\10 = \frac{2+2+3+4+4+5}{2}\text{.}\\ It could be planar, and then it would have 6 faces, using Euler's formula: \\6-10+f = 2\\ means \\f = 6\text{.}\\ To make sure that it is actually planar though, we would need to draw a graph with those vertex degrees without edges crossing. This can be done by trial and error (and is possible).

3

I'm thinking of a polyhedron containing 12 faces. Seven are triangles and four are quadralaterals. The polyhedron has 11 vertices including those around the mystery face. How many sides does the last face have?

Answer

Say the last polyhedron has \\n\\ edges, and also \\n\\ vertices. The total number of edges the polyhedron has then is \$7 \cdot 3 + 4 \cdot 4 + n)/2 = (37 + n)/2\text{.}\\ In particular, we know the last face must have an odd number of edges. We also have that \\v = 11 \text{.}\\ By Euler's formula, we have \\11 - (37+n)/2 + 12 = 2\text{,}\\ and solving for \\n\\ we get \\n = 5\text{,}\\ so the last face is a pentagon.

4

Consider some classic polyhedrons.

1. An *octahedron* is a regular polyhedron made up of 8 equilateral triangles (it sort of looks like two pyramids with their bases glued together). Draw a planar graph representation of an octahedron. How many vertices, edges and faces does an octahedron (and your graph) have?

2. The traditional design of a soccer ball is in fact a (spherical projection of a) truncated icosahedron. This consists of 12 regular pentagons and 20 regular hexagons. No two pentagons are adjacent (so the edges of each pentagon are shared only by hexagons). How many vertices, edges, and faces does a truncated icosahedron have? Explain how you arrived at your answers. Bonus: draw the planar graph representation of the truncated icosahedron.

3. Your “friend” claims that he has constructed a convex polyhedron out of 2 triangles, 2 squares, 6 pentagons and 5 octagons. Prove that your friend is lying. Hint: each vertex of a convex polyhedron must border at least three faces.

5

Prove Euler's formula using induction on the number of edges in the graph.

Answer

Proof

Let \\P(n)\\ be the statement, “every planar graph containing \\n\\ edges satisfies \\v - n + f = 2\text{.}\\” We will show \\P(n)\\ is true for all \\n \ge 0\text{.}\\ Base case: there is only one graph with zero edges, namely a single isolated vertex. In this case \\v = 1\text{,}\\ \\f = 1\\ and \\e = 0\text{,}\\ so Euler's formula holds. Inductive case: Suppose \\P(k)\\ is true for some arbitrary \\k \ge 0\text{.}\\ Now consider an arbitrary graph containing \\k+1\\ edges (and \\v\\ vertices and \\f\\ faces). No matter what this graph looks like, we can remove a single edge to get a graph with \\k\\ edges which we can apply the inductive hypothesis to. There are two possibilities. First, the edge we remove might be incident to a degree 1 vertex. In this case, also remove that vertex. The smaller graph will now satisfy \\v-1 - k + f = 2\\ by the induction hypothesis (removing the edge and vertex did not reduce the number of faces). Adding the edge and vertex back gives \\v - (k+1) + f = 2\text{,}\\ as required. The second case is that the edge we remove is incident to vertices of degree greater than one. In this case, removing the edge will keep the number of vertices the same but reduce the number of faces by one. So by the inductive hypothesis we will have \\v - k + f-1 = 2\text{.}\\ Adding the edge back will give \\v - (k+1) + f = 2\\ as needed. Therefore, by the principle of mathematical induction, Euler's formula holds for all planar graphs.

6

Prove Euler's formula using induction on the number of *vertices* in the graph.

7

Euler's formula (\\v - e + f = 2\$ holds for all *connected* planar graphs. What if a graph is not connected? Suppose a planar graph has two components. What is the value of \\v - e + f\\ now? What if it has \\k\\ components?

8

Prove that the *Petersen graph* (below) is not planar.

\![image-111.svg$$(https://math.libretexts.org/@api/deki/files/12951/image-111.svg?revision=1&size=bestfit&width=163&height=155)

\![$$(https://math.libretexts.org/images/image-111.svg)

Answer

What is the length of the shortest cycle? (This quantity is usually called the girth of the graph.)

9

Prove that any planar graph with \\v\\ vertices and \\e\\ edges satisfies \\e \le 3v - 6\text{.}\\

Answer

Proof

We know in any planar graph the number of faces \\f\\ satisfies \\3f \le 2e\\ since each face is bounded by at least three edges, but each edge borders two faces. Combine this with Euler's formula:

\begin{equation\*} v - e + f = 2 \end{equation\*} \begin{equation\*} v - e + \frac{2e}{3} \ge 2 \end{equation\*} \begin{equation\*} 3v - e \ge 6 \end{equation\*} \begin{equation\*} 3v - 6 \ge e. \end{equation\*}

10

Prove that any planar graph must have a vertex of degree 5 or less.

4.3: Coloring

1

What is the smallest number of colors you need to properly color the vertices of \\K\_{4,5}\text{?}\\ That is, find the chromatic number of the graph.

\![image-121.svg$$(https://math.libretexts.org/@api/deki/files/12952/image-121.svg?revision=1&size=bestfit&width=102&height=101) \![image-122.svg$$(https://math.libretexts.org/@api/deki/files/12953/image-122.svg?revision=1&size=bestfit&width=101&height=102) \![image-123.svg$$(https://math.libretexts.org/@api/deki/files/12954/image-123.svg?revision=1&size=bestfit&width=100&height=104) \![image-124.svg$$(https://math.libretexts.org/@api/deki/files/12955/image-124.svg?revision=1&size=bestfit&width=102&height=97) \![image-125.svg$$(https://math.libretexts.org/@api/deki/files/12956/image-125.svg?revision=1&size=bestfit&width=101&height=96)

Answer

2, since the graph is bipartite. One color for the top set of vertices, another color for the bottom set of vertices.

2

Draw a graph with chromatic number 6 (i.e., which requires 6 colors to properly color the vertices). Could your graph be planar? Explain.

Answer

For example, \\K_6\text{.}\\ If the chromatic number is 6, then the graph is not planar; the 4-color theorem states that all planar graphs can be colored with 4 or fewer colors.

3

Find the chromatic number of each of the following graphs.

\![$$(https://math.libretexts.org/images/image-121.svg) \![$$(https://math.libretexts.org/images/image-122.svg) \![$$(https://math.libretexts.org/images/image-123.svg) \![$$(https://math.libretexts.org/images/image-124.svg) \![$$(https://math.libretexts.org/images/image-125.svg)

Answer

The chromatic numbers are 2, 3, 4, 5, and 3 respectively from left to right.

4

A group of 10 friends decides to head up to a cabin in the woods (where nothing could possibly go wrong). Unfortunately, a number of these friends have dated each other in the past, and things are still a little awkward. To get the cabin, they need to divide up into some number of cars, and no two people who dated should be in the same car.

1. What is the smallest number of cars you need if all the relationships were strictly heterosexual? Represent an example of such a situation with a graph. What kind of graph do you get?

2. Because a number of these friends dated there are also conflicts between friends of the same gender, listed below. Now what is the smallest number of conflict-free cars they could take to the cabin?

| | | | | | | | | | | |

|----------------|-----|-----|-----|-----|-----|-----|-----|-----|-----|------|

| Friend | A | B | C | D | E | F | G | H | I | J |

| Conflicts with | BEJ | ADG | HJ | BF | AI | DJ | B | CI | EHJ | ACFI |

3. What do these questions have to do with coloring?

5

What is the smallest number of colors that can be used to color the vertices of a cube so that no two adjacent vertices are colored identically?

\![image-126.svg$$(https://math.libretexts.org/@api/deki/files/12957/image-126.svg?revision=1&size=bestfit&width=150&height=114)

Answer

The cube can be represented as a planar graph and colored with two colors as follows:

\![$$(https://math.libretexts.org/images/image-126.svg)

Since it would be impossible to color the vertices with a single color, we see that the cube has chromatic number 2 (it is bipartite).

6

Prove the chromatic number of any tree is two. Recall, a tree is a connected graph with no cycles.

1. \![image-127.svg$$(https://math.libretexts.org/@api/deki/files/12958/image-127.svg?revision=1&size=bestfit&width=177&height=132)

1. Describe a procedure to color the tree below.

2. The chromatic number of \\C_n\\ is two when \\n\\ is even. What goes wrong when \\n\\ is odd?

3. Prove that your procedure from part (a) always works for any tree.

4. Now, prove using induction that every tree has chromatic number 2.

7

Prove the 6-color theorem: every planar graph has chromatic number 6 or less. Do not assume the 4-color theorem (whose proof is MUCH harder), but you may assume the fact that every planar graph contains a vertex of degree at most 5.

8

Not all graphs are perfect. Give an example of a graph with chromatic number 4 that does not contain a copy of \\K_4\text{.}\\ That is, there should be no 4 vertices all pairwise adjacent.

Answer

The wheel graph below has this property. The outside of the wheel forms an odd cycle, so requires 3 colors, the center of the wheel must be different than all the outside vertices.

\![image-128.svg$$(https://math.libretexts.org/@api/deki/files/12959/image-128.svg?revision=1&size=bestfit&width=118&height=112)

\![$$(https://math.libretexts.org/images/image-128.svg)

9

Prove by induction on vertices that any graph \\G\\ which contains at least one vertex of degree less than \\\Delta(G)\\ (the maximal degree of all vertices in \\G\$ has chromatic number at most \\\Delta(G)\text{.}\\

10

You have a set of magnetic alphabet letters (one of each of the 26 letters in the alphabet) that you need to put into boxes. For obvious reasons, you don't want to put two consecutive letters in the same box. What is the fewest number of boxes you need (assuming the boxes are able to hold as many letters as they need to)?

Answer

If we drew a graph with each letter representing a vertex, and each edge connecting two letters that were consecutive in the alphabet, we would have a graph containing two vertices of degree 1 (A and Z) and the remaining 24 vertices all of degree 2 (for example, \\D\\ would be adjacent to both \\C\\ and \\E\$. By Brooks' theorem, this graph has chromatic number at most 2, as that is the maximal degree in the graph and the graph is not a complete graph or odd cycle. Thus only two boxes are needed.

11

Prove that if you color every edge of \\K_6\\ either red or blue, you are guaranteed a monochromatic triangle (that is, an all red or an all blue triangle).

4.4: Euler Paths and Circuits

1

You and your friends want to tour the southwest by car. You will visit the nine states below, with the following rather odd rule: you must cross each border between neighboring states exactly once (so, for example, you must cross the Colorado-Utah border exactly once). Can you do it? If so, does it matter where you start your road trip? What fact about graph theory solves this problem?

\![image-139.svg$$(https://math.libretexts.org/@api/deki/files/12960/image-139.svg?revision=1&size=bestfit&width=318&height=200)

\![$$(https://math.libretexts.org/images/image-139.svg)

Answer

This is a question about finding Euler paths. Draw a graph with a vertex in each state, and connect vertices if their states share a border. Exactly two vertices will have odd degree: the vertices for Nevada and Utah. Thus you must start your road trip at in one of those states and end it in the other.

2

Which of the following graphs contain an Euler path? Which contain an Euler circuit?

1. \\K_4\\

2. \\K_5\text{.}\\

3. \\K\_{5,7}\\

4. \\K\_{2,7}\\

5. \\C_7\\

6. \\P_7\\

Answer

1. \\K_4\\ does not have an Euler path or circuit.

2. \\K_5\\ has an Euler circuit (so also an Euler path).

3. \\K\_{5,7}\\ does not have an Euler path or circuit.

4. \\K\_{2,7}\\ has an Euler path but not an Euler circuit.

5. \\C_7\\ has an Euler circuit (it is a circuit graph!)

6. \\P_7\\ has an Euler path but no Euler circuit.

3

Edward A. Mouse has just finished his brand new house. The floor plan is shown below:

\![image-140.svg$$(https://math.libretexts.org/@api/deki/files/12961/image-140.svg?revision=1&size=bestfit&width=257&height=131)

\![$$(https://math.libretexts.org/images/image-140.svg)

1. Edward wants to give a tour of his new pad to a lady-mouse-friend. Is it possible for them to walk through every doorway exactly once? If so, in which rooms must they begin and end the tour? Explain.

2. Is it possible to tour the house visiting each room exactly once (not necessarily using every doorway)? Explain.

3. After a few mouse-years, Edward decides to remodel. He would like to add some new doors between the rooms he has. Of course, he cannot add any doors to the exterior of the house. Is it possible for each room to have an odd number of doors? Explain.

4

For which \\n\\ does the graph \\K_n\\ contain an Euler circuit? Explain.

Answer

When \\n\\ is odd, \\K_n\\ contains an Euler circuit. This is because every vertex has degree \\n-1\text{,}\\ so an odd \\n\\ results in all degrees being even.

5

For which \\m\\ and \\n\\ does the graph \\K\_{m,n}\\ contain an Euler path? An Euler circuit? Explain.

Answer

If both \\m\\ and \\n\\ are even, then \\K\_{m,n}\\ has an Euler circuit. When both are odd, there is no Euler path or circuit. If one is 2 and the other is odd, then there is an Euler path but not an Euler circuit.

6

For which \\n\\ does \\K_n\\ contain a Hamilton path? A Hamilton cycle? Explain.

Answer

Add texts here. Do not delete this text first.

All values of \\n\text{.}\\ In particular, \\K_n\\ contains \\C_n\\ as a subgroup, which is a cycle that includes every vertex.

7

For which \\m\\ and \\n\\ does the graph \\K\_{m,n}\\ contain a Hamilton path? A Hamilton cycle? Explain.

Answer

As long as \\\|m-n\| \le 1\text{,}\\ the graph \\K\_{m,n}\\ will have a Hamilton path. To have a Hamilton cycle, we must have \\m=n\text{.}\\

8

A bridge builder has come to Königsberg and would like to add bridges so that it *is* possible to travel over every bridge exactly once. How many bridges must be built?

Answer

If we build one bridge, we can have an Euler path. Two bridges must be built for an Euler circuit.

\![image-141.svg$$(https://math.libretexts.org/@api/deki/files/12962/image-141.svg?revision=1&size=bestfit&width=165&height=149)

\![$$(https://math.libretexts.org/images/image-141.svg)

9

Below is a graph representing friendships between a group of students (each vertex is a student and each edge is a friendship). Is it possible for the students to sit around a round table in such a way that every student sits between two friends? What does this question have to do with paths?\![image-142.svg$$(https://math.libretexts.org/@api/deki/files/12963/image-142.svg?revision=1)

\![$$(https://math.libretexts.org/images/image-142.svg)

Answer

We are looking for a Hamiltonian cycle, and this graph does have one:

\![image-143.svg$$(https://math.libretexts.org/@api/deki/files/12964/image-143.svg?revision=1&size=bestfit&width=181&height=176)

\![$$(https://math.libretexts.org/images/image-143.svg)

10

1. Suppose a graph has a Hamilton path. What is the maximum number of vertices of degree one the graph can have? Explain why your answer is correct.

2. Find a graph which does not have a Hamilton path even though no vertex has degree one. Explain why your example works.

11

Consider the following graph:

\![image-144.svg$$(https://math.libretexts.org/@api/deki/files/12965/image-144.svg?revision=1&size=bestfit&width=180&height=177)

\![$$(https://math.libretexts.org/images/image-144.svg)

1. Find a Hamilton path. Can your path be extended to a Hamilton cycle?

2. Is the graph bipartite? If so, how many vertices are in each “part”?

3. Use your answer to part (b) to prove that the graph has no Hamilton cycle.

4. Suppose you have a bipartite graph \\G\\ in which one part has at least two more vertices than the other. Prove that \\G\\ does not have a Hamilton path.

4.5: Matching in Bipartite Graphs

1

Find a matching of the bipartite graphs below or explain why no matching exists.

\![image-146.svg$$(https://math.libretexts.org/@api/deki/files/12966/image-146.svg?revision=1&size=bestfit&width=111&height=58) \![image-147.svg$$(https://math.libretexts.org/@api/deki/files/12967/image-147.svg?revision=1&size=bestfit&width=159&height=58) \![image-148.svg$$(https://math.libretexts.org/@api/deki/files/12968/image-148.svg?revision=1&size=bestfit&width=208&height=57)

\![$$(https://math.libretexts.org/images/image-146.svg) \![$$(https://math.libretexts.org/images/image-147.svg) \![$$(https://math.libretexts.org/images/image-148.svg)

Answer

The first and third graphs have a matching, shown in bold (there are other matchings as well). The middle graph does not have a matching. If you look at the three circled vertices, you see that they only have two neighbors, which violates the matching condition \\\card{N(S)} \ge \card{S}\\ (the three circled vertices form the set \\S\$.

\![image-149.svg$$(https://math.libretexts.org/@api/deki/files/12969/image-149.svg?revision=1&size=bestfit&width=121&height=63) \![image-150.svg$$(https://math.libretexts.org/@api/deki/files/12970/image-150.svg?revision=1&size=bestfit&width=153&height=57) \![image-151.svg$$(https://math.libretexts.org/@api/deki/files/12971/image-151.svg?revision=1&size=bestfit&width=230&height=62)

\![$$(https://math.libretexts.org/images/image-149.svg) \![$$(https://math.libretexts.org/images/image-150.svg) \![$$(https://math.libretexts.org/images/image-151.svg)

2

A bipartite graph that doesn't have a matching might still have a partial matching . By this we mean a set of *edges* for which no vertex belongs to more than one edge (but possibly belongs to none). Every bipartite graph (with at least one edge) has a partial matching, so we can look for the largest partial matching in a graph.

Your “friend” claims that she has found the largest partial matching for the graph below (her matching is in bold). She explains that no other edge can be added, because all the edges not used in her partial matching are connected to matched vertices. Is she correct?

\![image-152.svg$$(https://math.libretexts.org/@api/deki/files/12972/image-152.svg?revision=1&size=bestfit&width=194&height=99)

\![$$(https://math.libretexts.org/images/image-152.svg)

3

One way you might check to see whether a partial matching is maximal is to construct an alternating path . This is a sequence of adjacent edges, which alternate between edges in the matching and edges not in the matching (no edge can be used more than once). If an alternating path starts and stops with an edge *not* in the matching, then it is called an augmenting path .

1.

1. Find the largest possible alternating path for the partial matching of your friend's graph. Is it an augmenting path? How would this help you find a larger matching?

\![image-153.svg$$(https://math.libretexts.org/@api/deki/files/12973/image-153.svg?revision=1&size=bestfit&width=204&height=105)

2. Find the largest possible alternating path for the partial matching below. Are there any augmenting paths? Is the partial matching the largest one that exists in the graph?

​​​​​​​\![image-154.svg$$(https://math.libretexts.org/@api/deki/files/12974/image-154.svg?revision=1&size=bestfit&width=212&height=88)

\![$$(https://math.libretexts.org/images/image-154.svg)

4

The two richest families in Westeros have decided to enter into an alliance by marriage. The first family has 10 sons, the second has 10 girls. The ages of the kids in the two families match up. To avoid impropriety, the families insist that each child must marry someone either their own age, or someone one position younger or older. In fact, the graph representing agreeable marriages looks like this:

\![image-155.svg$$(https://math.libretexts.org/@api/deki/files/12975/image-155.svg?revision=1&size=bestfit&width=465&height=109)

\![$$(https://math.libretexts.org/images/image-155.svg)

The question: how many different acceptable marriage arrangements which marry off all 20 children are possible?

1. How many marriage arrangements are possible if we insist that there are exactly 6 boys marry girls not their own age?

2. Could you generalize the previous answer to arrive at the total number of marriage arrangements?

3. How do you know you are correct? Try counting in a different way. Look at smaller family sizes and get a sequence.

4. Can you give a recurrence relation that fits the problem?

5

We say that a set of vertices \\A \subseteq V\\ is a vertex cover if every edge of the graph is incident to a vertex in the cover (so a vertex cover covers the *edges*). Since \\V\\ itself is a vertex cover, every graph has a vertex cover. The interesting question is about finding a minimal vertex cover, one that uses the fewest possible number of vertices.

1. Suppose you had a matching of a graph. How can you use that to get a minimal vertex cover? Will your method always work?

2. Suppose you had a minimal vertex cover for a graph. How can you use that to get a partial matching? Will your method always work?

3. What is the relationship between the size of the minimal vertex cover and the size of the maximal partial matching in a graph?

6

For many applications of matchings, it makes sense to use bipartite graphs. You might wonder, however, whether there is a way to find matchings in graphs in general.

1. For which \\n\\ does the complete graph \\K_n\\ have a matching?

2. Prove that if a graph has a matching, then \\\card{V}\\ is even.

3. Is the converse true? That is, do all graphs with \\\card{V}\\ even have a matching?

4. What if we also require the matching condition? Prove or disprove: If a graph with an even number of vertices satisfies \\\card{N(S)} \ge \card{S}\\ for all \\S \subseteq V\text{,}\\ then the graph has a matching.

---

4_S_3A_Graph_Theory__Summary_

> 来源: LibreTexts

> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/4%3A_Graph_Theory/4.S%3A_Graph_Theory_(Summary)

Skip to main content

\\ \def\d{\displaystyle}\\

\\ \newcommand{\f}$$1$${\mathfrak \#1}\\

\\ \newcommand{\s}$$1$${\mathscr \#1}\\

\\ \def\N{\mathbb N}\\

\\ \def\B{\mathbf{B}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\Z{\mathbb Z}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\Q{\mathbb Q}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\R{\mathbb R}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\C{\mathbb C}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\F{\mathbb F}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\A{\mathbb A}\\

\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\

\\ \def\X{\mathbb X}\\

\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\

\\ \def\E{\mathbb E}\\

\\ \def\O{\mathbb O}\\

\\ \def\U{\mathcal U}\\

\\ \def\pow{\mathcal P}\\

\\ \def\inv{^{-1}}\\

\\ \def\nrml{\triangleleft}\\

\\ \def\st{:}\\

\\ \def\\{\widetilde}\\

\\ \def\rem{\mathcal R}\\

\\ \def\sigalg{\$\sigma\$-algebra }\\

\\ \def\Gal{\mbox{Gal}}\\

\\ \def\iff{\leftrightarrow}\\

\\ \def\Iff{\Leftrightarrow}\\

\\ \def\land{\wedge}\\

\\ \def\And{\bigwedge}\\

\\ \def\entry{\entry}\\

\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\

\\ \def\Vee{\bigvee}\\

\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\

\\ \def\imp{\rightarrow}\\

\\ \def\Imp{\Rightarrow}\\

\\ \def\Fi{\Leftarrow}\\

\\ \def\var{\mbox{var}}\\

\\ \def\Th{\mbox{Th}}\\

\\ \def\entry{\entry}\\

\\ \def\sat{\mbox{Sat}}\\

\\ \def\con{\mbox{Con}}\\

\\ \def\iffmodels{\bmodels\models}\\

\\ \def\dbland{\bigwedge \\\\\bigwedge}\\

\\ \def\dom{\mbox{dom}}\\

\\ \def\rng{\mbox{range}}\\

\\ \def\isom{\cong}\\

\\\DeclareMathOperator{\wgt}{wgt}\\

\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\

\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\

\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\

\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\

\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\

\\ \renewcommand{\v}{\vtx{above}{}}\\

\\ \def\circleA{(-.5,0) circle (1)}\\

\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\

\\ \def\circleB{(.5,0) circle (1)}\\

\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\

\\ \def\circleC{(0,-1) circle (1)}\\

\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\

\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\

\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\

\\ \def\ansfilename{practice-answers}\\

\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\

\\ \renewcommand{\bar}{\overline}\\

\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\ \newcommand{\lt}{<}\\

\\ \newcommand{\gt}{>}\\

\\ \newcommand{\amp}{&}\\

\\ \newcommand{\hexbox}$$3$${

  \def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}

  \def\y{-\r\*#1-sin{30}\*\r\*#1}

  \draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;

  \draw (\x,\y) node{#3};

}\\

\\\renewcommand{\bar}{\overline}\\

\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\

\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\

\\\newcommand{\lt}{\<}\\

\\\newcommand{\gt}{\>}\\

\\\newcommand{\amp}{&}\\

Hopefully this chapter has given you some sense for the wide variety of graph theory topics as well as why these studies are interesting. There are many more interesting areas to consider and the list is increasing all the time; graph theory is an active area of mathematical research.

One reason graph theory is such a rich area of study is that it deals with such a fundamental concept: any pair of objects can either be related or not related. What the objects are and what “related” means varies on context, and this leads to many applications of graph theory to science and other areas of math. The objects can be countries, and two countries can be related if they share a border. The objects could be land masses which are related if there is a bridge between them. The objects could be websites which are related if there is a link from one to the other. Or we can be completely abstract: the objects are vertices which are related if their is an edge between them.

What question we ask about the graph depends on the application, but often leads to deeper, general and abstract questions worth studying in their own right. Here is a short summary of the types of questions we have considered:

• Can the graph be drawn in the plane without edges crossing? If so, how many regions does this drawing divide the plane into?
• Is it possible to color the vertices of the graph so that related vertices have different colors using a small number of colors? How many colors are needed?
• Is it possible to trace over every edge of a graph exactly once without lifting up your pencil? What other sorts of “paths” might a graph posses?
• Can you find subgraphs with certain properties? For example, when does a (bipartite) graph contain a subgraph in which all vertices are only related to one other vertex?

Not surprisingly, these questions are often related to each other. For example, the chromatic number of a graph cannot be greater than 4 when the graph is planar. Whether the graph has an Euler path depends on how many vertices each vertex is adjacent to (and whether those numbers are always even or not). Even the existence of matchings in bipartite graphs can be proved using paths.

Chapter Review

1

Which (if any) of the graphs below are the same? Which are different? Explain.

\![$$(https://math.libretexts.org/images/image-156.svg) \![$$(https://math.libretexts.org/images/image-157.svg) \![$$(https://math.libretexts.org/images/image-158.svg)

Solution

The first and the third graphs are the same (try dragging vertices around to make the pictures match up), but the middle graph is different (which you can see, for example, by noting that the middle graph has only one vertex of degree 2, while the others have two such vertices).

2

Which of the graphs in the previous question contain Euler paths or circuits? Which of the graphs are planar?

Solution

The first (and third) graphs contain an Euler path. All the graphs are planar.

3

Draw a graph which has an Euler circuit but is not planar.

Solution

For example, \\K_5\text{.}\\

4

Draw a graph which does not have an Euler path and is also not planar.

Solution

For example, \\K\_{3,3}\text{.}\\

5

If a graph has 10 vertices and 10 edges and contains an Euler circuit, must it be planar? How many faces would it have?

Solution

Yes. According to Euler's formula it would have 2 faces. It does. The only such graph is \\C\_{10}\text{.}\\

6

Suppose \\G\\ is a graph with \\n\\ vertices, each having degree 5.

1. For which values of \\n\\ does this make sense?

2. For which values of \\n\\ does the graph have an Euler path?

3. What is the smallest value of \\n\\ for which the graph might be planar? (tricky)

Solution

1. Only if \\n \ge 6\\ and is even.

2. None.

3. 12\. Such a graph would have \\\frac{5n}{2}\\ edges. If the graph is planar, then \\n - \frac{5n}{2} + f = 2\\ so there would be \\\frac{4+3n}{2}\\ faces. Also, we must have \\3f \le 2e\text{,}\\ since the graph is simple. So we must have \\3\left(\frac{4 + 3n}{2}\right) \le 5n\text{.}\\ Solving for \\n\\ gives \\n \ge 12\text{.}\\​​​​​​​

7

At a school dance, 6 girls and 4 boys take turns dancing (as couples) with each other.

1. How many couples danced if every girl dances with every boy?

2. How many couples danced if everyone danced with everyone else (regardless of gender)?

3. Explain what graphs can be used to represent these situations.

Solution

1. There were 24 couples: 6 choices for the girl and 4 choices for the boy.

2. There were 45 couples: \\{10 \choose 2}\\ since we must choose two of the 10 people to dance together.

3. For part (a), we are counting the number of edges in \\K\_{4,6}\text{.}\\ In part (b) we count the edges of \\K\_{10}\text{.}\\

8

Among a group of \\n\\ people, is it possible for everyone to be friends with an odd number of people in the group? If so, what can you say about \\n\text{?}\\

Solution

Yes, as long as \\n\\ is even. If \\n\\ were odd, then corresponding graph would have an odd number of odd degree vertices, which is impossible.

9

Your friend has challenged you to create a convex polyhedron containing 9 triangles and 6 pentagons.

1. Is it possible to build such a polyhedron using *only* these shapes? Explain.

2. You decide to also include one heptagon (seven-sided polygon). How many vertices does your new convex polyhedron contain?

3. Assuming you are successful in building your new 16-faced polyhedron, could every vertex be the joining of the same number of faces? Could each vertex join either 3 or 4 faces? If so, how many of each type of vertex would there be?

Solution

1. No. The 9 triangles each contribute 3 edges, and the 6 pentagons contribute 5 edges. This gives a total of 57, which is exactly twice the number of edges, since each edge borders exactly 2 faces. But 57 is odd, so this is impossible.

2. Now adding up all the edges of all the 16 polygons gives a total of 64, meaning there would be 32 edges in the polyhedron. We can then use Euler's formula \\v - e + f = 2\\ to deduce that there must be 18 vertices.

3. If you add up all the vertices from each polygon separately, we get a total of 64. This is not divisible by 3, so it cannot be that each vertex belongs to exactly 3 faces. Could they all belong to 4 faces? That would mean there were \\64/4 = 16\\ vertices, but we know from Euler's formula that there must be 18 vertices. We can write \\64 = 3x + 4y\\ and solve for \\x\\ and \\y\\ (as integers). We get that there must be 10 vertices with degree 4 and 8 with degree 3. (Note the number of faces joined at a vertex is equal to its degree in graph theoretic terms.)​​​​​​​

10

Is there a convex polyhedron which requires 5 colors to properly color the vertices of the polyhedron? Explain.

Solution

No. Every polyhedron can be represented as a planar graph, and the Four Color Theorem says that every planar graph has chromatic number at most 4.

11

How many edges does the graph \\K\_{n,n}\\ have? For which values of \\n\\ does the graph contain an Euler circuit? For which values of \\n\\ is the graph planar?

Solution

\\K\_{n,n}\\ has \\n^2\\ edges. The graph will have an Euler circuit when \\n\\ is even. The graph will be planar only when \\n \lt 3\text{.}\\

12

The graph \\G\\ has 6 vertices with degrees \\1, 2, 2, 3, 3, 5\text{.}\\ How many edges does \\G\\ have? If \\G\\ was planar how many faces would it have? Does \\G\\ have an Euler path?

Solution

\\G\\ has 8 edges (since the sum of the degrees is 16). If \\G\\ is planar, then it will have 4 faces (since \\6 - 8 + 4 = 2\$. \\G\\ does not have an Euler path since there are more than 2 vertices of odd degree.

13

What is the smallest number of colors you need to properly color the vertices of \\K\_{7}\text{.}\\ Can you say whether \\K_7\\ is planar based on your answer?

Solution

\\7\\ colors. Thus \\K_7\\ is not planar (by the contrapositive of the Four Color Theorem).

14

What is the smallest number of colors you need to properly color the vertices of \\K\_{3,4}\text{?}\\ Can you say whether \\K\_{3,4}\\ is planar based on your answer?

Solution

The chromatic number of \\K\_{3,4}\\ is 2, since the graph is bipartite. You cannot say whether the graph is planar based on this coloring (the converse of the Four Color Theorem is not true). In fact, the graph is *not* planar, since it contains \\K\_{3,3}\\ as a subgraph.

15

A dodecahedron is a regular convex polyhedron made up of 12 regular pentagons.

1. Suppose you color each pentagon with one of three colors. Prove that there must be two adjacent pentagons colored identically.

2. What if you use four colors?

3. What if instead of a dodecahedron you colored the faces of a cube?

Solution

For all these questions, we are really coloring the vertices of a graph. You get the graph by first drawing a planar representation of the polyhedron and then taking its planar dual: put a vertex in the center of each face (including the outside) and connect two vertices if their faces share an edge.

1. Since the planar dual of a dodecahedron contains a 5-wheel, it's chromatic number is at least 4. Alternatively, suppose you could color the faces using 3 colors without any two adjacent faces colored the same. Take any face and color it blue. The 5 pentagons bordering this blue pentagon cannot be colored blue. Color the first one red. Its two neighbors (adjacent to the blue pentagon) get colored green. The remaining 2 cannot be blue or green, but also cannot both be red since they are adjacent to each other. Thus a 4th color is needed.

2. The planar dual of the dodecahedron is itself a planar graph. Thus by the 4-color theorem, it can be colored using only 4 colors without two adjacent vertices (corresponding to the faces of the polyhedron) being colored identically.

3. The cube can be properly 3-colored. Color the “top” and “bottom” red, the “front” and “back” blue, and the “left” and “right” green.

16

If a planar graph \\G\\ with \\7\\ vertices divides the plane into 8 regions, how many edges must \\G\\ have?

Solution

\\G\\ has \\13\\ edges, since we need \\7 - e + 8 = 2\text{.}\\

17

Consider the graph below:

\![$$(https://math.libretexts.org/images/image-159.svg)

1. Does the graph have an Euler path or circuit? Explain.

2. Is the graph planar? Explain.

3. Is the graph bipartite? Complete? Complete bipartite?

4. What is the chromatic number of the graph.

Solution

1. The graph does have an Euler path, but not an Euler circuit. There are exactly two vertices with odd degree. The path starts at one and ends at the other.

2. The graph is planar. Even though as it is drawn edges cross, it is easy to redraw it without edges crossing.

3. The graph is not bipartite (there is an odd cycle), nor complete.

4. The chromatic number of the graph is 3.

18

For each part below, say whether the statement is true or false. Explain why the true statements are true, and give counterexamples for the false statements.

1. Every bipartite graph is planar.

2. Every bipartite graph has chromatic number 2.

3. Every bipartite graph has an Euler path.

4. Every vertex of a bipartite graph has even degree.

5. A graph is bipartite if and only if the sum of the degrees of all the vertices is even.

Solution

1. False. For example, \\K\_{3,3}\\ is not planar.

2. True. The graph is bipartite so it is possible to divide the vertices into two groups with no edges between vertices in the same group. Thus we can color all the vertices of one group red and the other group blue.

3. False. \\K\_{3,3}\\ has 6 vertices with degree 3, so contains no Euler path.

4. False. \\K\_{3,3}\\ again.

5. False. The sum of the degrees of all vertices is even for *all* graphs so this property does not imply that the graph is bipartite.

19

Consider the statement “If a graph is planar, then it has an Euler path.”

1. Write the converse of the statement.

2. Write the contrapositive of the statement.

3. Write the negation of the statement.

4. Is it possible for the contrapositive to be false? If it was, what would that tell you?

5. Is the original statement true or false? Prove your answer.

6. Is the converse of the statement true or false? Prove your answer.

Solution

1. If a graph has an Euler path, then it is planar.

2. If a graph does not have an Euler path, then it is not planar.

3. There is a graph which is planar and does not have an Euler path.

4. Yes. In fact, in this case it is because the original statement is false.

5. False. \\K_4\\ is planar but does not have an Euler path.

6. False. \\K_5\\ has an Euler path but is not planar.​​​​​​​

20

Remember that a tree is a connected graph with no cycles.

1. Conjecture a relationship between a tree graph's vertices and edges. (For instance, can you have a tree with 5 vertices and 7 edges?)

2. Explain why every tree with at least 3 vertices has a leaf (i.e., a vertex of degree 1).

3. Prove your conjecture from part (a) by induction on the number of vertices. Hint: For the inductive step, you will assume that your conjecture is true for all trees with \\k\\ vertices, and show it is also true for an arbitrary tree with \\k+1\\ vertices. Consider what happens when you cut off a leaf and then let it regrow.

---