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

1
vote
2answers
71 views

A combinatorics question on a $n \times n$ grid

In the book 'Foundations of Data Science' by Hopcroft and Kannan, they have the following exercise (Ex. 5.46): Let G be a $n \times n$ lattice and let $S$ be a subset of $G$ with cardinality at ...
2
votes
0answers
35 views

Interesting Questions in Spectral Graph Theory

In the past, I have worked on few problems in Spectral graph theory and their applications to Physics. I have read parts of Fan Chung's book and Daniel Spielman lecture notes. I really enjoyed the ...
1
vote
1answer
40 views

Minimum degree and connectivity

Let $\delta$ denote the minimum degree of graph G. Show for every graph G, if G is connected and |V|>2$\delta$, then G has a path of length 2$\delta$. I started this way: Let P be the longest path ...
1
vote
1answer
28 views

Show that $m \le 2e/v \le M$

$G$ be a graph with $v$ vertices and $e$ edges.Let $M$ be maximum degree of the vertices of $G$, and let $m$ be the minimum degree of the vertices $G$.Show that $$m \le 2e/v \le M$$ I am completely ...
0
votes
1answer
50 views

How can one actually use Adjacency Matrix for understanding a graph?

I don't see any real reason why we would use an AM to represent a graph, beside visual appeal and ease. Generally, we would perform matrix operations on Matrices like |A|, Transpose and loads of other ...
-1
votes
0answers
39 views

The Petersen graph is vertex-transitive

How can you show that the Petersen Graph is vertex-transitive ? (You can't use the fact that the Petersen graph is isomorphic to any graph with vertices labelled $\binom{5}{2}$ where two vertices X ...
6
votes
1answer
210 views

Proving that G contains a cycle with at least $k+1$ edges

Let $k\geq 2$. Prove that if $G$ is $k$-regular, then $G$ contains a cycle with at least $k+1$ edges. The way I did it was to prove that the longest path in $G$ must have at least $k$ edges, and that ...
0
votes
2answers
68 views

Can you take off a sweater while wearing headphones?

This seems like a graph theory problem, but I'm not sure how to approach it. To clarify potential ambiguities, let's set up the situation. You are wearing a sweater (with one arm through each ...
0
votes
1answer
22 views

Understanding Kirchhoff's theorem

I am trying to the understand the Kirchhoff's theorem and it seems to be giving a hard time. Basically how do you explain why you have $n^{n-2}$ in finding the number of cycles in a given graph. A ...
1
vote
1answer
29 views

What multigraphs are isomorphic to their dual graph?

I arrived at this question by way of investigating knots, particularly the idea of "turning them inside out", in a sense. I called these their "complements". I noticed that the Borromean Rings ...
2
votes
2answers
161 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 ...
2
votes
8answers
2k views

Prove that every undirected finite graph with vertex degree of at least 2 has a cycle

Prove that every undirected finite graph with vertex degree of at least 2 has a cycle. Intuition-wise i need to prove that there's at least one 'tight -connection'. In other words, Proving that 2 ...
1
vote
0answers
24 views

Automorphism group of a bipartite regular graph

Showing an automorphism group of complete bipartite graph $K_{n,m}$ is easy. I'm wondering if there is an classification of automorphism groups of bipartite regular graphs. Did anyone heard something ...
1
vote
2answers
177 views

Regular graph (Homework)

Let $G = (V, E)$ be a graph and $ad(G) = \frac{2|E|}{|V|}$ the average degree of $G$. $$ mad(G) = max ( ad(H) : H \le G ) \text{ the maximum average degree of a subgraph of $G$} $$ We know that ...
-1
votes
2answers
50 views

Number of paths with length 3 in a wheel graph [closed]

How would I count the number of 3 length paths in a wheel graph where $n >= 2$?
0
votes
2answers
33 views

Finding paths in a graph with n vertices

Let n ≥ 2 be a natural number. Consider the graph G = (V, E) where V ={0,1,2,...,n} and E=({0,1},{0,2},...,{0,n}) ∪ ({1,2},...,{n−1,n}) ∪ ({n,1}) For paths, it's a sequence of (non-repeating) ...
2
votes
0answers
27 views

Existence of a Transversal in a Cycle

Let a transversal be defined as an independent set of $G$, containing precisely one vertex from each $V_i$. Let $G = (V,E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup \ldots \cup V_n$ be ...
0
votes
1answer
12 views

Removing a vertex from a non k-colorable graph cannot make it (k−2)-colorable

This is supposidly True in the key but a pentagon is non-4-colorable and removing a vertex (either deletion or contraction) leaves a 2 colorable graph. anyone know anything about this or is it just ...
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 ...
0
votes
1answer
36 views

Simple Cycle Graph proof

How can I show/prove that given a simple graph G with $n$ vertices, where $n$ is even, that if every vertex has degree $\frac{n}{2} + 1$, then G must contain a (simple) 3-cycle
0
votes
0answers
28 views

Diameter and maximal independent sets

I've proved that every nontrivial tree has at least two maximal indepndent sets, with equality only for stars via the bipartition of the trees. I am trying to extend that proof to general graphs, and ...
1
vote
1answer
63 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 ...
0
votes
2answers
54 views

Hamilton Graph and Complete Tripartite

1) Consider the complete tripartite graph $K_2,_3,_n$ for $n \ge 3$. Determine for what values of n the graph $K_2,_3,_n$ has a Hamilton path, and for what values of n the graph has a Hamilton cycle. ...
2
votes
1answer
24 views

Is there a name for a directed graph in which every vertex has outdegree one?

Per the question title, I'm dealing with a number of directed graphs, all of which are 1-out regular, and figure that there is probably a name for such a thing. Unfortunately, all my search attempts ...
0
votes
0answers
9 views

Find all vertices in a DAG with the property that none lie on any path with K edges and sum of weights ≥ Threshold

Given a DAG G with weights on the edges, all nodes have a blue color. We seek to color with red every path nodes with K edges such that the sum of weights of this path is greater than a threshold (T). ...
2
votes
1answer
30 views

Power of an adjacency matrix

For any adjacency matrix what does the power of it represent, you know like M^k ??? I guess what I'm wondering is, if I square it for example, what do the numbers correspond to??
2
votes
0answers
24 views

Probabilistic edge covers

Given a graph $G=(V,E)$ where every edge $ij$ has a corresponding probability $p_{ij}$. We can then consider random subsets of the edges $C \in E$ for which the probability that an edge $ij$ is ...
-6
votes
1answer
45 views

Discrete Math on Graphs [closed]

Can someone explain to me that how would I show that Is it possible for a simple graph with 6 vertices to have 42 edges?
-3
votes
1answer
40 views

Discrete Math On proving Graph Degree Sequence

Can someone please explain that how would I show or Prove that there is no graph with degree sequence (1, 1, 2, 3, 4, 4, 5, 7). Thanks
0
votes
1answer
20 views

Definition of a leaf in a tree

Across two different texts, I have seen two different definitions of a leaf 1) a leaf is a node in a tree with degree 1 2) a leaf is a node in a tree with no children The problem that I see with ...
1
vote
1answer
30 views

Elementary graph theory representation

We've been talking about graphs in class and my understanding is that $K_3$ means a graph $K$ has $3$ nodes. I have also been reading online to get a better understanding of what was said in class but ...
0
votes
2answers
35 views

Prove graph is bipartite

How can I prove that a graph $G = (V, E)$ is bipartite if and only if $G$ can be coloured with $2$ colors/colours? I know it's true, but don't know how to do it other than drawing every possible ...
2
votes
0answers
31 views

Maximum number of tile possible in 2048 game? [duplicate]

Ok my question is what is the maximum number of tile we can make in the 2048 game assuming we were really lucky and got all 4 number tiles and got the new squares exactly where we needed them?
1
vote
2answers
98 views

Why is the four coloring theorem so hard to prove when the five/six theorem proofs are much more accessible?

I might be giving a talk to high school students soon. I plan to show them the proof for the six/five coloring theorems and also give a brief discussion of the famous four color theorem. Why is the ...
1
vote
2answers
33 views

number of edges in the complement of a complete bipartite graph as a function of $n$, the toal number of verticies

Consider any complete bipartite graph $K_{p,q}$. Express the number of edges in $K_{p,q}^C$, the complement of $K_{p,q}$, as a function of $n$, the total number of verticies. Now, I know that I ...
10
votes
1answer
136 views

Probability that a random graph is planar

I've been attempting to solve the following challenge problem from a combinatorics class but am getting absolutely nowhere. Prove: For sufficiently large $n$, the probability a random graph ...
4
votes
1answer
1k views

Edge-coloring of bipartite graphs

A theorem of König says that Any bipartite graph $G$ has an edge-coloring with $\Delta(G)$ (maximal degree) colors. This document proves it on page 4 by: Proving the theorem for regular ...
0
votes
1answer
59 views

Finding Number of Edges and Vertices in Icosahedron

This is a practice question from a practice test I am working on. ...
0
votes
1answer
23 views

Connectivity of a graph

Lets say that I have a graph that looks like this: What does it mean if I take out one node in this case $6$ is it a valid argument to say that the graph still has $6$ edges? Or that is it an ...
0
votes
0answers
16 views

Undirected graphs and possible vertex relationships

Given an undirected graph with visible vertices but hidden edges, and with rules such as: node A connects with at least 2 other nodes node B connects with at least 1 other node node C connects with ...
1
vote
1answer
455 views

How to construct the graph from an adjacency matrix?

I have the following adjacency matrix: a b c d a [0, 0, 1, 1] b [0, 0, 1, 0] c [1, 1, 0, 1] d [1, 1, 1, 0] How do I draw the graph, given its adjacency ...
1
vote
1answer
38 views

Extending Euler's Formula for Connected Planar Graphs

I am trying to figure out how to extend Euler's formula, n - e + f = 2, to contain a connected component denoted k. I am new to graph theory so I am not sure if the way I got there is correct or if ...
1
vote
1answer
398 views

Expected number of simple, unordered cycles in a random graph

Consider an undirected random graph of $n$ vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}$. What is the expected number of simple (no vertex more than ...
0
votes
0answers
23 views

How to generate a list of representatives of graph isomorphism classes for small graphs?

I am trying to verify, using a Python program, that a conjecture about graphs holds, at least, for small graphs. In order to do this, I'm looking for a way to quickly generate a representative for ...
1
vote
2answers
23 views

If G is connected and order = size - 1 G is a Tree [duplicate]

to prove that, is it correct to proceed by contradicion and try to reach some conclusion like "if the order = size - 1 there can't be any cycles"? In that case, can you give me a hint of where to ...
1
vote
1answer
340 views

Maximum value for V in planar self-complementary graph

Let G=(V,E) be a simple and self complementary graph. What is the maximum number of vertices it can have if both it and its complement are planar when i) G is connected? ii)G is not necessarily ...
6
votes
1answer
343 views

Graph theory: for a connected graph, show that the size of the minimum vertex cover τ(G) is at most [(|E(G)| + 1)]/2

I'm having real trouble with this practice question: Show that $$\tau(G) ≤ \frac{|E(G)| + 1}{2}$$ for every connected graph G. What properties of a connected graph entail this inequality? Does ...
1
vote
1answer
40 views

Probability that exists at least an edge in the configuration model

In this period, I am studying some topics on random networks to understand the modularity optimization used in community detection. In particular, I am trying to understand a model called ...
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. ...
4
votes
2answers
440 views

maximum flow ford-fulkerson analysis

I am reading about maximum flows in Introduction to algorithms by Cormen etc. Ford-Fulkerson algorithm is given below. FORD-FULKERSON(G, s, t) ...