2
votes
2answers
34 views

Proving corollary to Euler's formula by induction

I'm currently looking at two proofs to the following corollary to Euler's formula and I'm not quite seeing how the authors can make a specific assumption in their proof. One proof comes from my ...
1
vote
1answer
34 views

Prove that if graph $G$ is a 3-connected planar graph then its dual must be simple.

I'm trying to study for a quiz. I think I'm on the right track with this problem, however, I'm having a difficult time formalizing it. Prove that if graph $G$ is a 3-connected planar graph then its ...
0
votes
0answers
62 views

Prove that a certain graph and its dual are 4-colorable

Let $G$ be a simple planar graph with fewer than 12 faces. Suppose that each vertex of $G$ has degree at least $3$. prove that $G$ and its dual are 4-colorable. I'm not too sure how to approach ...
2
votes
2answers
158 views

Help with graph induction proof

I'm trying to prove : Given a simple graph G with n vertices, where n is even, prove that if every vertex has degree n/2 + 1, then G must contain a (simple) 3-cycle. A (simple) 3-cycle is a set of 3 ...
0
votes
1answer
26 views

Proof for a graph distance

For Graph $G$, there are several $(x, y)$-paths; the shortest among them have length $2$. Thus $d(x, y) = 2$. Prove that graph distance satisfies the triangle inequality. That is, if $x,y,z$ are ...
1
vote
1answer
60 views

Using Pigeonhole Principle for a graph proof

Using the Pigeonhole Principle, prove that in any graph with two or more vertices there must exist two vertices that have the same degree. (Note: the problem does not assume that the graph is ...
1
vote
2answers
46 views

Prove for a simple graph that $n-1 \leq m \leq \frac{n(n-1)}{2}$

For a given simple (that is neither loops nor multiple edges are allowed) undirected graph, where $m$ is the number of edges and $n$ is the number of vertices that the following inequality holds. ...
1
vote
1answer
50 views

Prove thoroughly: If the degree of all vertices is greater or equal to $\frac{|V| - 1}{2}$, then the simple graph is connected.

I am struggling to write a good, thorough proof. The proof is supposed to be logically rigorous, correct and complete (e.g. no hidden assumption). Moreover, style is important - the proof should be ...
1
vote
0answers
45 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
14
votes
6answers
641 views

Can an algorithm be part of a proof?

I am an undergraduate student. I have read several papers in graph theory and found something may be strange: an algorithm is part of a proof. In the paper, except the last two sentences, other ...
0
votes
1answer
43 views

Depth of BFS Tree With Different Root Nodes

I need to either prove or disprove that for any node of a graph, the depth of the BFS tree using this node as root is always the same. My intuition is that this is true, but I'm having difficulty ...
1
vote
2answers
220 views

Prove Four Statements Are Equivalent

I have the following problem, where $G$ is a graph with $n$ vertices, prove the following statements are equivalent: 1. $G$ is connected and acyclic 2. $G$ is connected and has $n-1$ edges 3. $G$ ...
2
votes
1answer
65 views

Are these two proofs regarding coloring valid and complete?

Question #1) Prove or disprove: If G is a graph and for every vertex $v \in V(G), \chi (G-v) < \chi (G)$, then for every subgraph H such that $H \neq G, \chi(H) < \chi(G)$. Question #2) Prove ...
1
vote
1answer
809 views

Solving graph theory proofs

I am trying to study for an exam on graph theory and I have a few questions. How would you start a proof? For example, when I see a problem like this: Let G be a graph with n vertices where every ...
0
votes
1answer
77 views

how to prove a result

I was studying about graph operation on wiki. Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and $|V_1|$ copies of $G_2$ ($|V_1|$ is the number ...
0
votes
1answer
31 views

Is this graph transitive?

I have a graph $G = (A,B)$ which is transitive when: $(a,b) ∈ B ∧ (b,c) ∈ B → (a,c) ∈ B$. How can I prove that $G$ is transitive iff it's acyclic?
0
votes
1answer
17 views

Question about graphs and relations

If I have a directed graph $G = (V,E)$, let the relation $R$= {$(a,b)$ | $a$ has a directed path to $b$} be a relation over $V$. How can I prove that $R$ is an equivalence relation, partial order, ...
0
votes
3answers
43 views

If $G$ is disconnected and the vertices $x,y$ are adjacent in $G$, then there is a vertex that isn't adjacent to $x$ and isn't adjacent to $y$.

I'm just starting graph theory and I'm trying to prove the following: Let $G$ be a simple disconnected graph with vertex set $V(G)$ and edge set $E(G)$. If $x,y\in V(G)$ and $xy \in E(G)$, then ...
0
votes
0answers
75 views

Hamiltonian cycle problem: how to prove NP-completeness?

How to prove that finding a Hamiltonian cycle in a graph is an NP-complete problem? Should I try to reduce the travelling salesman problem (TSP) to this one (Hamiltonian cycle)?
1
vote
1answer
159 views

$G$ is a tree $\iff G$ contains no cycles, but if you add one edge you create exactly one cycle - is my proof correct?

$G$ is a tree $\iff G$ contains no cycles, but if you add one edge you create exactly one cycle Could anyone please be so kind to check my proof? That would be very much appreciated. Thank you in ...
2
votes
1answer
285 views

Proof the sum of the square of the in and out degree are the same [duplicate]

I know by the handshaking theorem that in a graph, the sum of the in degree and the sum of the out degree will be the same. I observe that in a complete directed graph (as in a complete graph that has ...
7
votes
2answers
211 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
2
votes
2answers
80 views

eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
1
vote
1answer
75 views

Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
2
votes
0answers
269 views

The Dinitz Problem - proof

This theorem is the one that the proof is for Consider $n^2$ cells arranged in an $(n × n)$-square, and let $(i, j)$ de- note the cell in row $i$ and column $j$. Suppose that for every cell ...
2
votes
1answer
615 views

Checking if my proof for path and walk in graph theory is correct

I am trying to prove that if there exists a walk in a graph from $v$ to $w$, then there exists a path in the graph from $v$ to $w$ where $v$ and $w$ are vertices of graph $g$... I am not sure if I ...
1
vote
3answers
213 views

Non-isomorphic connected graphs question

How do I find all of the non-isomorphic connected graphs with the degree sequence 233345?
2
votes
2answers
101 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 ...
1
vote
1answer
363 views

Connected planar graph with girth $\leq$ 6 $\rightarrow$ exists at least one vertex degree $\leq 2$

Having trouble with how to approach this question: Suppose $G$ is a connected planar graph having girth at least $6.$ Prove that $G$ has at least one vertex with degree at most $2.$
4
votes
3answers
303 views

If a graph of $2n$ vertices contains a Hamiltonian cycle, then can we reach every other vertex in $n$ steps?

Problem: Given a graph $G,$ with $2n$ vertices and at least one triangle. Is it possible to show that you can reach every other vertex in $n$ steps if $G$ contains a Hamilton cycle (HC)? EDIT: ...
13
votes
3answers
580 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
3answers
3k views

A finite graph with exactly two vertices with odd degree must have a path joining them.

I would really appreciate it if anyone would validate if my argument ( proof ? ) for the above statement is valid. I am aware of other proofs but the current argument is more of a task in ...
3
votes
2answers
309 views

Properties of Connected Graphs

How would I start going about proving these properties? Prove that the following three properties of a CONNECTED graph $G$ are equivalent: $G$ has no cycles. $G$ is a graph on $N$ vertices with ...
0
votes
1answer
749 views

Minimum Dominating Set and Minimum Vertex Cover Proof

I am working on a proof for the following description: Let D and C be a minimum dominating set and a minimum vertex cover of a connected graph G, respectively. Prove that $|D| \leq |C|$. My thinking ...
1
vote
1answer
466 views

Vertex Cover Proof

I am working on an exercise describe like so: Without using knowledge about cliques, prove that a graph G has an independent set of size k if and only if G has a vertex cover of size n - k where n is ...
0
votes
1answer
738 views

Clique and Independent Set Proof

I am currently working on an exercise that is described like so: Prove that a graph $G$ has a clique of size $k$ if and only if $\overline{G}$ has an independent set of size $k$, where ...
8
votes
1answer
2k views

If a graph has no cycles of odd length, then it is bipartite: is my proof correct?

I came up with a proof of Graph $G$ has no cycles of odd length $\implies$ $G$ is bipartite. like this: Without loss of generality, let's only consider a connected component, because if every ...