Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
0answers
13 views

Prove that Hall's Condition is necessary for complete matching

Here's what I have so far: Hall's Algorithm states that given $n$ girls and $n$ boys a complete matching between the two groups is possible iff any of the three conditions are satisfied: There is ...
-2
votes
0answers
16 views

Use adjacency matrix of a graph to solve for number of walks between vertices. [on hold]

Let $A=\begin{bmatrix} 1 &2 &0\\ 2 &1 &2\\ 0&2&1\end{bmatrix}$ be the adjacency matrix of a graph $G$ with vertices $v_1, v_2, v_3.$ Find (a) the number of walks of length 2 ...
0
votes
0answers
29 views

Using Hall's Theorem to show something.

Suppose that there are five young women and five young men on an island. Each man is willing to marry some of the women on the island and each woman is willing to marry any man who is willing to marry ...
1
vote
1answer
21 views

Prove that if G is a graph with no even cycles, then every cycle in G is an induced subgraph.

I tried using the contrapositive to prove the original statement: If no cycle in G is an induced subgraph, then G is a graph with no odd cycles. To prove this, I assumed that G did have an odd cycle ...
1
vote
1answer
10 views

How many edges could a cross-section of a polyhedron have?

We know that the cross-section of a cube could have 3, 4, 5, or 6 edges. But there could be no more. This can be explained in many ways: (1) The number of edges of a cross-section can't exceed the ...
0
votes
1answer
20 views

Maximum edge of a directed graph , if it contains weak components?

A digraph includes n nodes , and has two weak components , what is the maximum number of edges? ( there is no directed cycle)? Another question ,how does the answer change , if there is two strong ...
2
votes
1answer
61 views

Furthest distance vertices undirected tree

I know in my mind that it's very obvious, but I just can't seem to prove the following statement: Let $G$ be an undirected non-trivial tree with at least $3$ vertices. Let $u$ be an arbitrary vertex ...
1
vote
1answer
31 views

Planar Graph faces

let $G$ be a planar graph Prove that in any planar embedding of $G$, number of faces with odd degree is even. Also, prove that if G is not bipartite, then there are at least 2 faces with odd degree. ...
-2
votes
1answer
23 views

Prove that if $uv$ is a bridge in a graph $G$ then there is a unique $uv$ path in $G$ [on hold]

Prove that if $uv$ is a bridge in a graph $G$ then there is a unique $uv$ path in $G$.
0
votes
1answer
22 views

Graph skeleton for thorus $S_1$

Suppose the $g=1$ platonic graph with degree $d=3$ and the number of edges bounding each face is $n=6$ ($v=14$). Is this the skeleton of $S_1$ (the thorus with one hole)? We know that $K_7$ and the ...
1
vote
1answer
14 views

Deriving the probability of a node (vertex) on the end of a random chosen link (edge) having degree d.

From Jackson - Social and Economic Networks p. 87 (link: http://press.princeton.edu/chapters/s4_8767.pdf p.12 in pdf): (...) (T)he distribution of degrees of a node found by choosing a link ...
3
votes
0answers
44 views

Number of subgraphs in the ladder graph

Assume you have the usual (in both directions infinite) ladder graph. I can try to provide a picture if needed. Further assume the vertices are labelled and I have one distinct vertex (call it the ...
0
votes
0answers
23 views

Modifying Kruskal's algorithm for Maximum Spanning Tree

So in our class, we did a proof on Kruskal's algorithm for finding Minimum Spanning Tree. Now, based on that, I have to modify it to find me a Maximum Spanning Tree. I know the idea, taking ...
0
votes
1answer
16 views

Let $r\geq 4$ and let $\delta (G)> (1-\frac{1}{r-1})|G|$. Show that every edge is contained in a $K_r$

Let $r\geq 4$ and let $\delta (G)> (1-\frac{1}{r-1})|G|$. Show that every edge is contained in a $K_r$ Hint: Pick the remaining vertices of the $K_r$ one by one. I'm at a loss as to what to do, ...
2
votes
1answer
30 views

How many subgraphs does a $4$-cycle have?

Question: How many subgraphs does a $4$-cycle have? I am trying to discover how many subgraphs a $4$-cycle has. I know that there will be $2^4=16$ subgraphs with no edges, but I am not sure how to ...
1
vote
1answer
41 views

Collection of spanning trees for a simple connected graph

Consider a graph $G$ whose edges are labelled $\{1, 2, ..., k\}$. Then the set of spanning trees is a collection of subsets of $[k]$. a) Let $T$ = $\{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}$. Can $T$ be ...
0
votes
0answers
17 views

Best set of subgraphs of a weighted complete bipartite graph

Consider a weighted complete bipartite graph, i.e. consider the graph $G=(V,E)$, with $V=X \cup Y$, $X \cap Y = \emptyset$ and $E = X \times Y$, and a set of weights $W=\{w_i : i \in E\}$. Now we ...
1
vote
2answers
26 views

Proof related to maximum degree of node in a graph

So I'm given this problem - Prove that in every graph with 25 vertices, in which holds that in every 3-subset of vertices, at least two of them are connected, there exists a node of degree at least ...
0
votes
1answer
20 views

Hamiltonian circuit in a Hamming graph

The problem is exactly what I have asked here: Showing that a particular graph is Hamiltonian Let $Q:=\{1,2,\ldots, q\}$. Let $G$ be a graph with the elements of $Q^n$ as vertices and an edge ...
1
vote
1answer
42 views

Tree-related problem, counting leafs

I am studying Graph Theory right now, and I have solved tons of problems so far. However, I got a tree-related problem, where it asks me to prove that a tree, in which maximum node degree is 6, the ...
1
vote
0answers
15 views

small expected contraction embedding into trees?

I learned FRT theorem for probabilistic metric embedding into trees: For any finite metric d, there exists a distribution over non contracting, small expected expansion tree metrics. The theorem can ...
0
votes
2answers
56 views

How many ways can the image be properly colored with at most q colors?

so the actual question is about the 8 regions of Iceland's political map, I just remapped it where each vertex is a different region and the edges represent which regions it boarders.The way I ...
1
vote
0answers
22 views

Chromatic number for sets of five or more elements

Definition. Given the set $D$ of positive integer numbers, we construct the distance graph for the integers, which vertices are $\Bbb{Z}$ and two numbers $x$ and $y$ are connected if the ...
0
votes
0answers
19 views

Probabilty of a path of length $D$ crossing partition exactly $k$ times

I am faced with a graph theory and probability question while doing my systems research. Suppose i have a Graph $G = (V,E)$ with $|V|$ vertices and $|E|$ edges. Now I partition the graph in $n$ parts ...
3
votes
1answer
25 views

Proofs involving some general formulae for trees and binary trees.

So here I have 3 tree-related questions. 1) Let $n\geq2$ and let $d_1 ≤d_2 ≤···≤d_n$ be a sequence of integers. Show that there is a tree with degree sequence $d_1,d_2,...,d_n \Leftrightarrow \sum ...
1
vote
1answer
22 views

Establishing a bijection between binary vectors and threshold graphs.

So this is a theorem in my notes... A graph is threshold if and only if it can be created by means of two operations - starting with a single vertex 1) Add a dominating vertex (adjacent to all ...
0
votes
1answer
38 views

Prove that if $n$ is odd, then $C_n$ is antimagic.

Prove that if $n$ is odd, then $C_n$, the cyclic graph of $n$ vertices, is antimagic. How would you construct and write the proof for this problem?
6
votes
1answer
45 views

On an $h \times h$ square lattice, count all the paths from $(0,a)$ to $(h-1,b)$, $a,b \in [0,h-1]$, with diagonal moves allowed

Consider an $h \times h$ upright square lattice, where a point is defined by $(x,y)$, $x,y \in [0,h-1]$. A valid path starts from the left boundary, $(0,a)$, $ a \in [0,h-1]$ and ends to the right ...
-1
votes
0answers
11 views

The Tree-Doubling Algorithm [on hold]

The Tree-Doubling Algorithm, starting the Euler tour and the Hamilton cycle at the vertex a and resolving any ties alphabetically.Show all relevant steps of the procedure. Can anyone help with this. ...
1
vote
2answers
22 views

Prove that every maximal planar graph of order 4 or more is 3-connected

I thought I might be able to use the fact that for a maximal planar graph the minimum degree of the graph is at least 3, but I couldn't figure anything out. Am I headed in the right direction? Where ...
0
votes
1answer
23 views

What is the sum at each vertex of a super-magic labeling of Kn,n? Explain your answer.

What is the sum at each vertex of a super-magic labeling of Kn,n? Explain your answer. I know that the sum at each vertex of K3,3 equals 15 and K4,4 the sum at each vertex is 34, but I don't know ...
0
votes
0answers
29 views

On Tree- Doubling Algorithm

Use the Tree-Doubling Algorithm, starting the Euler tour and the Hamilton cycle at the vertex a and resolving any ties alphabetically. Need help to this question. Thanking you.
-2
votes
1answer
25 views

PigeonHole Principle - Question [on hold]

10 points are within a unit square. Prove there must be a pair of points with distance (from one another) is less than $0.48$
0
votes
1answer
30 views

Number of nonisomoprhic planar graphs

How many nonisomoprhic planar graphs (V, E) are there with |V| = 6 and |E| = 10 assuming that each vertex has degree ≥ 3?
0
votes
1answer
25 views

Prove a planar graph is unique up to isomorphisms

Find a planar graph with 12 vertices and such that all vertices have degree 5. Show that such a graph is unique modulo isomorphism. I know we can find the number of faces and edges using Euler's ...
0
votes
1answer
30 views

Number of triangles in a planar graph

Assume that G = (V, E) is a planar graph. If G has 8-vertices and 13 edges then what can be a minimal possible number of triangular regions? What can be a maximal possible number of triangular ...
2
votes
1answer
70 views

Combinatorial graph theory proof

Why does $\binom{1/2}{n+1} * (-1)^n * 2^{2*n+1}$ equal $1/(n+1) * \binom{2n}{n}$? I came across this in an exercise in Graph Theory and Its Applications by Gross and Yellen. I haven't been able to ...
0
votes
1answer
17 views

What conditions on a graph $G$ allow it to be uniquely determined by the spectrum of $A(G)$?

What conditions on an undirected graph $G$ allow it to be uniquely determined by the spectrum of its adjacency matrix $A(G)$? Very simple examples show that one needs connectivity, and I imagine ...
0
votes
0answers
12 views

Number of vertices on graph with k blocks

Let $G$ be a graph on $n$ vertices and $B_1,B_2, \dots, B_k$ be all the blocks of $G$. Prove that $n = \sum_{i=1}^k |V(B_i)|-k+1$. Intuitively this makes sense since I believe you could decompose the ...
0
votes
4answers
36 views

Determine all graphs with matching number = 1

Determine all graphs G, without isolated vertices, such that the matching number=1. Could anyone help me this question? I am really confused about it. How to determine all possible graphs with this ...
1
vote
1answer
22 views

bipartite graph has perfect matching

Let G be a connected U-W bipartite graph,the cardinality of U and W is equal and at least two. And the degrees of the vertices in U are all different. Prove thatG contains a perfect matching. ...
0
votes
3answers
36 views

Find All NonIsomorphic Undirected Graphs with Four Vertices

The Full Question Find all(loop-free) non-isomorphic, undirected graphs with four vertices. How many of these graphs are connected? My Work(Ideas) I'm a little infuriated at this question because ...
0
votes
0answers
24 views

How to find the width knowing clique number

For an interval order, clique number=chromatic number (which is the minimum number of colors you can use for each edge to be incident to vertices that are of different colors). I also read that clique ...
2
votes
1answer
14 views

Removing a node from a tree causes it to become a disjoint union of disjoint paths

Question: Let T be a Tree of exactly $k\ge2$ leafs. $v\in V(T)$ is a vertex s.t $deg(v)\ge k$. Prove that $T-v$ is a disjoint union of $k$ non empty disjoint paths. My solution: Induction Base: if ...
1
vote
1answer
20 views

Prove that a graph is connected if and only if for every partition of its vertices into two nonempty sets

Prove that a graph is connected if and only if for every partition of its vertices into two nonempty sets, there is an edge with endpoints in both sets. My proof: Let $V=V(H)$ where $H$ is not ...
0
votes
1answer
38 views

Finding minimum paths in Graph theory

A Canadian postman, rather than returning to the post office $(p)$ after delivering mail along every street in town, wishes to return straight home $(h)$. Let $G$ be a connected graph and $p , h $ ...
0
votes
1answer
32 views

Relationship between parameters in graph

I am quite sure that there is such constant c and I think it's 2 (or smaller?), but I am unable to prove it. edit: avg(G) means average distance in graph G
1
vote
1answer
21 views

Discrete Mathematics Graphs

I need help about something. I would like to draw a cubic graph (each node has to have degree $3$) $G=(V,E)$, $|V|=2n$, where $n\geq 3$ (it doesn't matter, it can be $3,4,7$ etc). But this graph must ...
2
votes
1answer
35 views

Finding a subgraph with smaller clique number without removing a clique the size of the clique number.

Given an infinite graph $G$, with clique number $2< \omega (G) < \infty$, is it possible to remove vertices such that the remaining subgraph has clique number $\omega (G)-1$, under the ...
0
votes
0answers
14 views

Topological minor and independence number

If $G$ and $X$ are graphs with $G=TX$, ($X$ is a topological minor of $G$) is there any sort of relation between $\alpha(G)$ and $\alpha(X)$ (the independence numbers of both). In addition if finding ...