First to describe the following graphs, in the bipartite graphs, the red edges indicate an edge which is part of the matching whereas the black edges are dotted out. Furthermore, in the flow networks, the red arcs are the saturated arcs, whereas black arcs are unsaturated. Furthermore, above each vertex, there is a list starting with some value (Inf, None, 0 or 1) this indicates the label of the vertex. Additionally, the remaining values in the list are the flow and capacity of the arc and the order is from top to bottom visually. As in for example 0/1, 1/1, 0/1, 0/1 indicates that the top, 3rd and bottom arcs have 0 flow and capacity of 1 whereas the arc underneath the top and above the 3rd has flow 1.
![[MatchingPa.svg]]
![[Flow1b.svg]]
Step 1:
![[FlowCiA.svg]]
![[FlowCiB.svg]]
![[Pasted image 20241013234229.png]]
The images above are in order, the labeling process, the updated flow, the labels again and the augmented path.
ii)
![[FlowCiiA.svg]]
![[FlowCiiB.svg]]
![[Pasted image 20241013235659.png]]
The same order applies to this second iteration.
Now the last iteration would just label vertex and terminate, thus we would find that if , then the minimum cut and maximum flow of 8.
![[MatchingPd.svg]]
The following graph displays the graph of where is the graph drawn in blue and the edges added are drawn in red. Note how this graph is thus it is not 3 colourable.
![[Pasted image 20241013232559.png]]
We will prove that for every tree with maximum degree 3, that is 4-colourable by induction on .
First, we know that by the definition of .
Now let be the statement "For any tree of vertices with maximum degree 3, is 4-colourable".
For the case , since only has a single vertex, then . This implies that is 4-colourable (since it is 1-colourable).
Now for suppose is true.
Let be an arbitrary tree with vertices and maximum degree 3. Let be a leaf vertex in . Let be the only vertex adjacent to . Now by the definition of we know that since . However, we also know that , therefore, . Furthermore, we can note that since every vertex has , therefore, any vertex has a distance greater than 2 (since for any 2 distinct vertices there is only one unique -path between them).
Now consider , by our inductive hypothesis, we know that is 4-colourable.
Furthermore, we also know that . Therefore, there are at most 3 colours assigned to the neighbours of . So we can assign an unused colour to . Therefore, since is 4-colourable and we can assign a colour without needing a 5th colour. Then is 4-colourable.
Thus, by the Principle of Mathematical Induction is true .
Below is a graph of where is drawn in blue and and the edges added to create are drawn in red. Note how this graph is thus it is not 5-colourable.
![[Pasted image 20241013232737.png]]
Proof: Every tree with maximum degree 3, is 6-colourable.
We will begin by showing that for any rooted tree with maximum degree 3, root and , there exists 2 distinct leaves, and such that where is the parent of and .
For some rooted tree , we will call 2 vertices siblings if they both share a parent.
First, let be an arbitrary rooted tree where every vertex we have or when is a leaf with and root .
Let be a leaf with maximal distance from and let be the parent of . Since and has maximal distance from , then (since there would be a leaf with larger distance from than ).
Let be a child of such that , which we can note that . However, we can also note that is also a leaf being that if it had a child then which would mean that wasn't the leaf with maximum distance from . Therefore both and are maximum distance from .
Let a tree be 3-maximal if every vertex of the tree has degree 3 except for the leaves which have degree 1.
We will now show for any 3-maximal tree that is 5-degenerate by induction on .
First, we know that by the definition of .
Now let be the statement "For any 3-maximal tree of vertices, is 5-degenerate".
Consider the case of . Any graph with is 5-degenerate since the maximum degree of such a graph is 5. Therefore, for a 3-maximal tree with vertices, must be 5-degenerate.
Now consider , suppose is true.
Let be a 3-maximal tree with vertices. Let be leaves such that where is a vertex which is adjacent to both and .
Now let for be the sets of vertices of distance from .
Since we know that .
We also know that since is 3-maximal, then , thus (we remove since it has shorter distance than 2) where is a 3rd vertex adjacent to (we already have and ). Lastly, we have (we remove since has distance shorter than 3 to ), since we know then we know .
Furthermore, for every vertex , every vertex has distance , thus we only need to consider and .
Now for the graph we have thus by our inductive hypothesis, is 5-degenerate. However, since for we add edges between any vertices with distance less than or equal to 3, we can consider . Mainly, the set of vertices in with distance less than or equal to 3 is given by and we know since , and .
Nevertheless, since is 5-degenerate and then we know that any subgraph of will have minimum degree at most 5.
Thus by the Principle of Mathematical Induction is true .
We can now also consider a non 3-maximal tree with maximum degree of 3.
Since such a tree would reduce the size of any vertices neighbourhood (before it had either 3 elements or 1, now it can also have 2), the above proof still remains valid.
Now we can use Theorem 28 from the notes which states that any -degenerate graph is -colourable.
Thus, since is 5-degenerate, it is 6-colourable.
Bellow is a drawing of the graph in (a) with the blue edges used to indicate which edges and vertices are used to find a subdivision of the graph which is also a subdivision of
![[Pasted image 20241013233237.png]]
Looking at both graphs it is easy to see that the second graph is a subdivision of the first graph. Furthermore, it is also easy to notice that the second graph is a subdivision of . Thus by Kuratowski's theorem, we know that the graph in (a) is non planar
![[Pasted image 20241013233231.png]]
Below is a drawing of the graph in (b) with no edge crossings. Since such a drawing exists, thus the graph in (b) is planar.
![[Pasted image 20241013233122.png]]
A graph has no subgraph if and only if every block of is either an isolated vertex, a bridge or a cycle.
proof:
()
Consider a graph with no subgraph then none of the blocks of can contain a subgraph either (otherwise would contain a subgraph).
Now consider the blocks consisting of either an isolated vertex or a bridge. We can easily see that for an isolated vertex there does not exist a path from to . Furthermore, for a bridge with vertices there only exists internally disjoint path from to .
If we now consider the maximal biconnected blocks, let be a biconnected block. Now, suppose, by way of contradiction that is not a cycle.
By biconnectivity, any 2 vertices there exists a cycle through them. Let be the cycle subgraph of with the most vertices. Let be the graph with the edges of removed. Now, by our assumption, since is not a cycle, then , otherwise, which implies is a cycle. Now let be 2 distinct vertices such that there exists an -path in between them (since there is at least 1 edge in we know that such a path exists). Now since , there exists 2 internally disjoint -paths in . Additionally, there exists at least 1 internally disjoint -path between them. Therefore, in there exists at least 3 internally disjoint -paths, thus we have a contradiction. Therefore, can only be a cycle.
()
We will now prove the contrapositive, such that if a graph has a subgraph then there exists a block which is not cycle, bridge or isolated vertex. Let be a graph with a subgraph
We can note that a graph consists of at least 4 vertices since there must exist a vertex with in order to have 3 internally disjoint paths. Furthermore, we can also note that a graph has no cut vertex and that it is connected. Therefore, a graph is a biconnected graph. Additionally, the blocks of consist of isolated vertices, bridges and maximal biconnected graphs. Since a graph has more than 4 vertices, it can't be a subgraph of an isolated vertex or a bridge, therefore, it is a subgraph of some maximal biconnected block . However, we can easily note that is not a cycle (since the subgraph is not a cycle).
Thus, we have shown that if a graph has a subgraph, then there exists a block of which is not an isolated vertex, bridge or a cycle
We can find that the maximum number of edges occurs when every block is a triangle, this yields the following equations.
If is the number of blocks in then the number of edges is .
This is due to each block sharing a vertex (if they don't then we can't maximise the number of edges).
However, we can find using the number of vertices in such a graph that therefore .
Thus with equality for even when is connected and every block is a triangle and for odd when is connected, a single block is a bridge and the remaining blocks are triangles.
Proof:
We will prove that via induction on the number of vertices.
Let be the statement "A graph with no subgraph has ."
Let's first consider the case of . Since there is only a single vertex then and , thus is true.
Now for suppose is true.
Let be a graph with no subgraph, Let .
Case 1: There exists an isolated vertex .
If we were to delete vertex we would get a graph which would also not have a subgraph, thus would have vertices and by our inductive hypothesis has . However since then we know that as required.
Case 2: There exists a vertex with .
If a vertex has degree of 1,
A graph with no subgraphs and with odd vertices has if and only if every block is a triangle and is connected.
Alternatively, for a graph with no subgraphs and with odd vertices has if and only if is connected, 1 block is a bridge or a 4-cycle and the remaining blocks are triangles.
