2
votes
0answers
35 views

IS this proof by induction of the hand shake lemma correct?

Proof by induction that the sum of degrees of vertexes in an undirected graph equals two times the number edges, where $V$ is the set of vertexes and $E$ is an edge multiset: $$\sum_{v ∈ V} deg(v) = ...
0
votes
2answers
40 views

The maximum no. of edges in a DISCONNECTED simple graph…

... on n vertices when it is not connected being equal to (1/2)(n - 1)(n - 2)... I can see that for n = 1 & n = 2 that the graphs have no edges... however I don't understand how to derive this ...
0
votes
2answers
160 views

Help showing that every walk of length $k$ from $x$ to $y$ in a graph is a path.

If I were to suppose $x$ and $y$ are two vertices in the same connected component of a graph, and let $k$ be the distance between them, how would I prove that every walk of length $k$ from $x$ to $y$ ...
3
votes
0answers
36 views

An undirected graph $G$ can be decomposed into simple edge-disjoint cycles if and only if all of its vertices have even degree.

Research effort: $\rightarrow)$ I think this is relatively easy. $\leftarrow)$ Let $G = (V,E)$, let $w$ be any vertex of $G$, given that all the vertex have even degree, I'm assured that I can ...
1
vote
1answer
23 views

Prove that every subgraph of forest has at least one vertex of degree < 2

So I know that a forest is a graph that has no cycles. This is what I had in mind: Assume that we have the subgraph T, which has two options: to be connected or not. if it's connected it has to be a ...
2
votes
1answer
47 views

Proof involving maximum weight of edge in minimum spanning tree

Let $G$ be a minimum spanning tree of a complete graph. Let $e$ be the maximum weight edge in $G$. I'd like to proof that given any other spanning tree $G'$ of this graph, being $j$ the maximum weight ...
0
votes
1answer
47 views

Proof for binary tree is a planar graph

Suppose G is a binary tree. Is G necessarily planar? Give a proof, or a counterexample. My guess is that it is indeed planar but I am struggling to find a formal proof for this. EDIT: Is there a ...
0
votes
1answer
27 views

Proof homomorphism between graphs

Given two graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$, an homomorphism of $G_1$ to $G_2$ is a function $f:V_1 \rightarrow V_2$ such $(v,w) \in E_1 \rightarrow (f(v),f(w)) \in E_2$. We establish that ...
0
votes
1answer
27 views

Proof that a local minimum in a spanning tree is also a minimum spanning tree.

Be $G$ a connected graph with weights associated to its edges. Be $T(G)$ the graph that has the spanning trees of $G$ as vertex, and two spanning trees are adjacent to each other if and only if each ...
3
votes
3answers
83 views

If a connected graph has a unique spanning tree, then it is a tree.

Prove if a connected graph has a unique spanning tree, then it is a tree. Edit: This can be shown with proof by contradiction.
0
votes
1answer
29 views

Let $G$ be a graph with radius $r$ and let $x$ be a vertex in the center of $G$. If $d$($x,y$)=$r$, then $y$ is in the periphery of $G$

Prove, disprove, or give a counterexample: Let $G$ be a graph with radius $r$ and let $x$ be a vertex in the center of $G$. If $d$($x,y$)=$r$, then $y$ is in the periphery of $G$. Eccentricity - the ...
0
votes
1answer
44 views

Proof that any self-complementary graph has to have $4k$ or $4k+1$ vertex, for some $k \in \mathbb N$

I've seen looking on previous questions that using this algorithm, I can construct self-complementary graphs. I got confused at this point, because I'm not sure if I should proof that there are no ...
1
vote
2answers
40 views

Finding quantity of vertex of odd degree in a graph

Let $G=(V,X)$. If $G$ has n vertex, such exactly $n-1$ have odd degree, how many vertex of odd degree have $\overline {G}$. ($\overline {G}$ the complement of $G$.) So the first thing I notice is ...
2
votes
1answer
16 views

Proof that in a graph of $2$ or more vertrex, there's at least $2$ of them that have the same degree

That's what I what to prove let $G$ be an undirected graph such it has $2$ or more vertex, there's at least $2$ vertex that have the same degree. I'm almost certain that, supposing that it's possible ...
0
votes
1answer
54 views

Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
1
vote
2answers
65 views

Let $G$ be a connected graph. If $G$ has no cut vertices, then G has no bridges.

Prove, disprove, or give a counterexample: Let $G$ be a connected graph. If $G$ has no cut vertices, then $G$ has no bridges.
1
vote
1answer
30 views

If the edge $xy$ is a bridge of $G$, then $x$ and $y$ are in separate components of $G$-$xy$.

If the edge $xy$ is a bridge of $G$, then $x$ and $y$ are in separate components of $G$-$xy$. I can't think of a counterexample so I am operating under the impression that it can be proved. How does ...
1
vote
3answers
70 views

Prove that a graph with $n$ vertices and less than $n$-1 edges, is disconnected.

Prove that if $G$ is a graph with $n$ vertices and fewer than $n$-1 edges, then $G$ is disconnected. The book I am working through uses a similar definition of "$n$ vertices and at least $n$-1 edges, ...
0
votes
1answer
24 views

Proving a circuit of a graph will have an edge in common with a cycle of the same graph.

Prove, if possible, if an edge lies on a circuit in $G$, then the edge also lies on a cycle in $G$. I attempted to find a counterexample but it seems pretty evident that this statement is true. The ...
2
votes
0answers
101 views

Finding minimum graph of $k$ disjoints component

Sorry for the english, I tried to make it the most clear possible. Be $G$ a connected graph not directed, I have to find an algorithm that given $n$ the quantity of vertex and $0<k<n$ disjoint ...
2
votes
1answer
71 views

Spanning trees in planar dual graph

The amount of spanning trees in a planar graph G is equal to the amount of spanning trees in the dual graph G*. I would like to proove this, i know it's true, but i would like to show that it holds ...
2
votes
2answers
78 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
87 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
74 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
240 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
67 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
86 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
51 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
59 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
48 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
14
votes
6answers
708 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
53 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
270 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
66 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
1k 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
87 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
50 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
82 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
197 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
428 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
215 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
88 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
82 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
275 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
799 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
223 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
108 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
424 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.$