Given a minimal non-planar graph G, we need to find out if G', which is G-e, where e is a removed edge, we need to prove that there exists an edge e such that its removal would make G' a maximal planar graph.
My idea in trying to figure this out would be by taking a minimal non-planar graph and...
How do we describe a construction of a 2-colorable graph where the degree of every vertex is greater than or equal to (|V|-1)/2? Based on that, what can be said about the dependence of maximum vertex-degree on k-colorability of a graph?
My first thought is that in order for a vertex to connect...
Our problem involves a graph G that is simple and connected, where every biconnected component is a cycle that has at least four vertices in it. The maximum number of components we can get from removing a cut vertex is 4, and we are asked to find tight bounds on the chromatic number of G.
My...
If we combine the cycles that all share a given vertex together, then they should form a mbc?
If I assume that all graphs smaller than some size have the property, is it the same as assuming that for k vertices the graph G has all even degrees and also in all its maximal biconnected components...
Honestly the more and more I think about this problem the more confusing it gets.
If the graph G has all even vertices and we want to then show its maximal biconnected components have all of their vertex as even degrees, then I guess that since you have an even graph then every vertex must have...
I was studying for my class a bit today and came across this video explaining that all the vertices in a graph have even degrees if and only if there is a cycle decomposition of that graph. I assume that cycles can be biconnected components because similar to mbc's, if we remove one edge, the...
I would say that there is still a path, because since we have at least two vertices that can reach u and two that can reach v, removing only one vertex can remove at most one path to either u and v, so there is still a way to get from w to w'
I think an edge cannot belong to two mbc's because every vertex on an mbc needs two paths to that vertex, so we'd need to have at least two edges connecting an mbc which would just make those two mbc's one maximal component and makes a violation?
The endpoints of an edge if it's in an mbc have to be incident to two or more edges including that edge. So if we remove that endpoint, we'd be removing more than two edges from the mbc.
I don't think an edge can be in two mbc's. If an edge is part of an mbc, so if we remove it from the mbc it should still be connected if we remove one of its vertices. However, if that edge is connecting two mbcs, A and B, if we remove a vertex of that edge in A, does that disconnect A? Would it...
Ok, so an edge cannot belong to two mbc because that would mean that the degree of the two incident vertices of the two mbc's would be odd. But if we connected edges so that we had an even number of edges from each vertex of the two mbc's that connected them both, then that makes a contradiction...
My logic was that for a vertex to have any degree, it must have an edge connecting it to another vertex (I assume that this graph is simple). But an edge is its own mbc, so then the number of vertices coming from any edge in G must be itself even, since connected graphs are just a union of mbcs(?)
I think I better understand now. The G' graph I created wouldn't exist because those two vertices and the line across from them is their own maximal biconnected component on it's own. However, is it true that two vertices and an edge between them is biconnected, since removing one vertex removes...
If G doesn't have to have all of it's vertices even, when the problem states: "t for graph G, ∀v ∈ V (G) : d(v) is even iff for every maximal biconnected component Bi ∈ G, ∀u ∈ V (Bi) : d(u) is even" that v and u refer to the same vertices?
In that case, the first direction (Show that if a...
This part is where I'm having trouble though, with the traingle example you just provided, as two components all six vertices would have degree 2; however if we connected them in G, then the two vertices from the traingles used for that edge would then have degree 3