这是一次图论exam代写
Graph Theory
Test 1
Please upload this rst page with your Academic Honesty Statement. Please
read the following and sign.
I hereby con rm that this assignment represents my own work. I con rm that it
has been completed in adherence to the Senate Policy on Academic Honesty, without
unapproved collaboration or the use of unpermitted aids or resources. This includes:
Conferring with classmates or any other person while the exam is in progress.
Posting questions to any websites for any reason.
I recognize the importance of academic integrity and understand that there is no
tolerance towards academic dishonesty within the the Department of Mathematics
and Statistics. I am aware that any suspected breaches will be reported, investigated,
and may result in additional penalties in accordance with the Academic Honesty
Policy.
Name:
Signature:
(a) What is the fewest number of edges possible in a graph with 10 vertices and 3 components? Give an example of such a graph.
(b) What is the most number of edges possible in a simple graph with 10 vertices and 3 components? Describe an example of such a graph with the maximum number of edges. DO NOT TRY TO DRAW THE GRAPH.
We know that in general, the minimum number of edges is $n-k$ where $n$ is the order of the graph and $k$ is the number of components. So, in this case, 7 is the minimum number of edges. $P_{8}$ together with two isolated points would be such a graph. 1 pt for the number of edges, 1 point for the justification, 2 points for the example.
The most number of edges in general is $\frac{(n-k)(n-k+1)}{2}$, so, in this case, the most number of edges possible is $28 .$ An example of such a graph is $K_{8}$ together with two isolated points. 1 pt for the general result, 1 pt for the number of edges, 2 pts for the example.
(a) Explain why a connected graph $H$ of order $n$ with $n-1$ edges has no cycles.
(b) Explain why any graph of order $n$ with no cycles and $n-1$ edges must be connected.
The minimum number of edges of a connected graph of order $n$ is $n-1$. But if a graph of order $n$ has a cycle, removing an edge from the cycle leaves the graph connected. But if the graph has $n-1$ edges, removing any edge disconnects the graph. So a graph of order $n$ with $n-1$ edges can’t have any cycles.
Noting that a removing an edge from a cycle leaves a graph connected
Noting that removing an edge from a graph of order $n$ with $n-1$ edges disconnects the graph
Each compenent is connected with no cycles, so is a tree. So each component has $n-1$ edges. So if there are $k$ components, there must be $n-k$ edges. So there is only 1 component.
(a) Give an example of a tournament on 5 vertices that is not Hamiltonian, or explain why no such graph exists.
(b) Give an example of a tournament on 5 vertices that is semihamiltonian and another that is Hamiltonian.
A complete graph oriented with every edge at one vertex pointed the same direction (either all directed out of the vertex or all directed into the vertex) cannot be Hamiltonian since there is no cycle including that vertex.
Any tournament that is not hamiltonian must be semi-hamiltonian. so the graph from the previous problem is semi-Hamiltonian.
Any tournament with a clearly indicated directed cycle would suffice.
(a) Give an example of a connected not strongly connected graph. 2 points for any such graph, 4 points for a graph with $\delta(G) \geq 2$.
Grading scheme given in problem. any graph with a bridge works.
(b) Can there be a regular graph of degree 4 that is connected but not strongly connected?
I had meant to ask if any such graph is orientable. And the answer to that is yes. Any such graph (without directions assigned to edges) is Eulerian and so has a cycle passing through every vertex and edge. Orienting the cycle in a single direction making it a directed cycle would make the graph a strongly connected digraph. The notion of strongly connected is only applicable to digraphs. So the question: Is every regular digraph of degree 4 strongly connected. I.e,. is every orientation of a regular graph of degree 4 strongly connected and the answer to that is no (fix a vertex and have all edges oriented into that vertex).
(a) Give an example of a graph that is 2-edge connected but not 3 -edge connected.
Grading scheme given in problem. any graph with a bridge works.
(b) Explain why $\kappa(G) \leq \delta(G)$.
Suppose the order of $G$ is $n . \kappa(G) \leq n-1$ by definition. If $\delta(G)=n-1$ we are done. If $\delta(G)<n-1$. Take the vertex $v$ of order $\delta(G)$. Let $S$ be all the vertices adjacent to $v$. Then $G-S$ has at least 2 vertices and leaves $v$ isolated. So $G-S$ is disconnected and so $\kappa(G) \leq|S|=\delta(G)$.
(a) In the Peterson Graph, true or false: any two nonadjacent vertices have exactly one common neighbour. Explain.
(b) In class we asserted that the Peterson graph has a 9 cycle. Draw the Peterson graph, label the vertices and write down the sequence of vertices that form the 9 -cycle.
TRUE. The vertices of the Peterson graph the two element subsets of ${1,2,3,4,5}$. If $v$ and $w$ are non-adjacent vertices, they must have an element in common, so $v={a, b}$ and $w={a, c}$ with $b \neq c$. So ${a, b, c}$ takes up three elements of ${1,2,3,4,5}$, so there is only one two element set disjoint from both. So only one vertex adjacent to both.
