Tagged Questions
2
votes
1answer
89 views
How to show a graph is not Hamiltonian?
Suppose you are given a graph $G$ with the properties that $G$ is 3-regular, $v_G = 10$ where $v_G$ is the number of vertices in $G$, and girth$(G) \geq 5$. How can you tell that $G$ is not ...
0
votes
0answers
59 views
A procedure for Topological sort, proof for its correctness.
Definition: A preserved invariant of a state machine is a predicate, $P$, on
states, such that whenever $P(q)$ is true of a state, $q$, and $q \rightarrow r$ for some state, $r$,
then $P(r)$ holds.
...
1
vote
2answers
73 views
Theorem of Eulerian Path
I am a little bit confused by the proof of Theorem 1.8.1 (Euler 1736) on the page 23 of the textbook Graph Theory by Diestel.
Theorem 1.8.1 (Euler 1736)
A connected graph is Eulerian if and only if ...
0
votes
0answers
25 views
Second-Order Random Choice Proof
Given $G = (V,E)$ ;$ |V| = n, |E| = m$ then choose $T$ with $t$ vertices uniformly
I have to proof the graph theory as $$E[X] - E[Y] \geq a$$
Which
$$E[X] \geq \frac{(2m)^t}{n^{2t-1}}$$
X is random ...
2
votes
3answers
97 views
Proof that a n-hypercube is n-vertex-connected
I'm new to graph theory, I'm finding it hard to get upon proofs.
To prove: An n-hypercube is n-vertex connected. Approaches I thought:
It holds true for n=2, so ...
4
votes
2answers
154 views
Short proof for the non-Hamiltonicity of the Petersen Graph
It is well known that the Petersen Graph is not Hamiltonian. I can show it by case distinction, which is not too long - but it is not very elegant either.
Is there a simple (short) argument that the ...
2
votes
2answers
77 views
If a graph has no isolated or pendant vertices then it contains at least one simple circuit
I am trying to prove that if a finite graph has no isolated or pendant vertices then it contains at least one simple circuit.
Let the graph with no isolated or pendant vertices be $(V,E)$. A path in ...
2
votes
2answers
50 views
Prove that if you have 2 trails of max length possible, in a connected graph, then them share a vertex.
What I'm wanting to prove is what it says in the title of the question.
Or more formally:
$P=(V_p,E_p)$, $Q=(V_q,E_q)$ are two trails of the max length possible / G=(V,E) a connected graph, $(V_p ...
3
votes
0answers
131 views
Combinatorics and graph theory - counting connected graphs
We denote by $C(n,n+k)$ the number of connected graphs on $n$ vertices with $n+k$ edges. I have 2 problems I wish to prove, but after much effort have gotten nowhere with. I would greatly value some ...
0
votes
0answers
63 views
Does a Minimum Spanning Tree entail minimum cost between 2 vertices?
In a graph, if I expand a vertex to a minimum spanning tree, does this entail that the path(s) obtained by walking from the start vertex to any other vertex along the tree are minimal? Thanks
6
votes
1answer
108 views
Application of the First Moment Method to Random Graphs
I've been trying for a few days to figure out a proof of part $(iii)$ of Lemma 2.1 of this paper, on page 4, and I could definitely use some help. You don't need to understand any of the rest of the ...
11
votes
3answers
410 views
Counterexamples to proofs of correct statements
This question is in part inspired by a quote I saw in an answer to another question:
The problem with incorrect proofs to correct statements is that it is hard to come up with a counterexample.
...
0
votes
1answer
250 views
Maximal number of bridges for a given vertex count and minimal degree
For the problem statement below, what would be best way to prove it? I have a solution which I think is not very elegant which is why I am asking this question:
Prove that no graph on 100 vertices ...
0
votes
2answers
666 views
k×k grid has tree-width at least k
I am looking for ideas how to solve the problem from Diestel's textbook Graph Theory.
Chapter 12. Minors, Trees, and WQO.
Problem 16. Apply Theorem 12.3.9 to show that the $k \times k$ grid has ...
2
votes
1answer
76 views
Family of graphs with treewidth $\leq k$ is minor-closed
I try to prove that,
For any integer $k$, the graphs with treewidth at most $k$ define a minor-closed family.
At first the idea of the proof doesn't seem to be complicated.
Let's say we have ...
3
votes
2answers
151 views
Proving that crossing number for a graph is the lowest possible
How would one go about proving that the crossing number for a graph is the lowest possible?
To be more specific, given a specific representation of a particular cubic graph $G$, how do I prove that ...
1
vote
1answer
281 views
Problem with proving Hall marriage theorem
I have a question about the proof of this theorem. If modeled with graphs, theorem would go like this:
Marriage problem:
Let $V_1$ and $V_2$ be the disjunct set of vertices in a bipartite graph, ...
3
votes
2answers
703 views
How do I write this proof more formally?
So the question asks, given that we have a undirected graph with unique edge weights, prove that the graph has a unique minimum spanning tree.
My Proof:
If the graph has unique edge weights, we can ...
3
votes
1answer
309 views
Prove : In a connected weighted Graph G, Kruskal's Algorithm constructs a minimum spanning tree
Background:
I was studying Theorem 2.3.3 from Introduction to Graph Theory by W. B. West. The main idea of his proof is as follows:
T, resulting tree.
T *, spanning tree of minimum weight.
Let, T ...
